网站没有h1标签,深圳市住建局,保定模板建站定制网站,wordpress未收到验证码文章目录 一、排序1、排序的各种方式分类 二、插入排序1、直接插入排序2、希尔排序3、希尔排序时间复杂度分析 三、选择排序1、直接选择排序2、堆排序 四、交换排序1、冒泡排序2、快速排序3、快速排序hoare找基准值4、快排挖坑法找基准值5、前后指针法6、快速排序非递归实现 五… 文章目录 一、排序1、排序的各种方式分类 二、插入排序1、直接插入排序2、希尔排序3、希尔排序时间复杂度分析 三、选择排序1、直接选择排序2、堆排序 四、交换排序1、冒泡排序2、快速排序3、快速排序hoare找基准值4、快排挖坑法找基准值5、前后指针法6、快速排序非递归实现 五、归并排序1、递归实现2、非递归实现 六、排序算法复杂度及稳定性分析七、计数排序 一、排序 在生活中各种场景中都会有排序的身影存在在网购时会有价格排序在学校中会有程序排序在游戏中会有段位的排序等。 1、排序的各种方式分类 这些排序的效率各有不同 二、插入排序 直接插⼊排序是⼀种简单的插⼊排序法其基本思想是把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中直到所有的记录插⼊完为⽌得到⼀个新的有序序列 。 1、直接插入排序 当插⼊第 i(i1) 个元素时前⾯的 array[0],array[1],…,array[i-1] 已经排好序此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较找到插⼊位置即将 array[i] 插⼊原来位置上的元素顺序后移 代码实现
void InsertionSort(int* arr, int n)
{int i 0;int j 0;for ( i 1; i n; i){j i-1;int tmp arr[i];while (j 0){if (arr[j] tmp){arr[j 1] arr[j];j--;}else{break;}}arr[j 1] tmp;}
}2、希尔排序 直接插入排序效率不高在直接插入排序的基础上进行优化改进把一个大的集合分为若干个小的集合再进行直接插入排序从而提升效率。 希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是先选定⼀个整数通常是gap n/31把待排序⽂件所有记录分成各组所有的距离相等的记录分在同⼀组内并对每⼀组内的记录进⾏排序然后gapgap/31得到下⼀个整数再将数组分成各组进⾏插⼊排序当gap1时就相当于直接插⼊排序。 代码实现
void ShellSort(int* arr, int n)
{int gec n;int i, j 0;while (gec 1){gec gec / 3 1;for (i gec; i n; i){j i - gec;int tmp arr[i];while (j 0){if (arr[j] tmp){arr[j gec] arr[j];j - gec;}else{break;}}arr[j gec] tmp;}}
}3、希尔排序时间复杂度分析 外层循环的时间复杂度可以直接给出为 O(log2 n) 或者 O(log3 n) 即 O(log n) 内层循环 希尔排序的时间复杂度大约为 log 2 n 1.3 \log_2 {n^{1.3}} log2n1.3 三、选择排序 每⼀次从待排序的数据元素中选出最⼩或最⼤的⼀个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 1、直接选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int max begin, min begin;for (int i begin 1; i end; i){if (a[i] a[min]){min i;}if (a[i] a[max]){max i;}}if (max begin){max min;}{int tmp a[min];a[min] a[begin];a[begin] tmp;}{int tmp a[max];a[max] a[end];a[end] tmp;}begin;end--;}
}2、堆排序
void HeapSort(int* arr, int n)
{int i 0;for (i (n-1)/2; i0; i--){int parent i;int child parent * 2 1;while (child i){if (child 1 i arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){int tmp arr[parent];arr[parent] arr[child];arr[child] tmp;parent child;child parent * 2 1;}else{break;}}}for (i n - 1; i 0; i--){int child i;int parent 0;int tmp arr[parent];arr[parent] arr[child];arr[child] tmp;child parent * 2 1;while (child i){if (child 1 i arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){tmp arr[parent];arr[parent] arr[child];arr[child] tmp;parent child;child parent * 2 1;}else{break;}}}
}堆排序的时间复杂度为n log n \log n logn 四、交换排序
1、冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int falg 1;for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;falg 0;}}if (falg){break;}}
}2、快速排序 通过找基准值基准值的位置就是这个值该待的位置然后递归找基准值左边区间和右区间直到区间不成立位置确定每个值该待的位置完成排序。 int _QuickSort(int* a, int left, int right)
{int keyi left;left;while (left right){while (left right a[left] a[keyi]){left;}while (left right a[right] a[keyi]){right--;}if (left right){int tmp a[left];a[left] a[right];a[right] tmp;left;right--;}}int tmp a[keyi];a[keyi] a[right];a[right] tmp;return right;
}void QuickSort(int* a, int left,int right)
{if (left right){return;}int keyi _QuickSort(a, left, right);QuickSort(a, keyi 1, right);QuickSort(a, left, keyi - 1);}快排的空间复杂度O( l o n g n long n longn) 快排的时间复杂度O(n l o n g n long n longn) 3、快速排序hoare找基准值 //快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int keyi left;left;while (left right){while (left right a[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}if (left right){swap(a[left], a[right]);}}swap(a[keyi], a[right]);return right;
}4、快排挖坑法找基准值
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int hole left;int tmp a[hole];while (left right){while (left right a[right] tmp){right--;}a[hole] a[right];hole right;while (left right a[left] tmp){left;}a[hole] a[left];hole left;}a[hole] tmp;return hole;
}5、前后指针法
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int pfast left 1;int pslow left;int keyi left;while (pfast right){while (pfast right a[pfast] a[keyi] pslow ! pfast){swap(a[pslow], a[pfast]);}pfast;}swap(a[pslow], a[keyi]);return pslow;
}6、快速排序非递归实现
// 快速排序 非递归实现//运用栈数据结构
typedef int StackDataType;typedef struct Stack
{int* a;int capacity;int top;
}ST;//栈初始化
void STInit(ST* ps)
{ps-a NULL;ps-capacity ps-top 0;
}//入栈
void STPush(ST* ps,StackDataType x){if (ps-capacity ps-top){int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;int* tmp (int*)realloc(ps-a, newcapacity * sizeof(StackDataType));if (tmp NULL){perror(realloc fail);return;}ps-capacity newcapacity;ps-a tmp;tmp NULL;}ps-a[ps-top] x;
}//判断栈是否为空
bool STEmpty(ST* ps)
{return ps-top 0;
}//出栈
void STPop(ST* ps)
{if (ps-top 0){return;}ps-top--;
}//取栈顶元素
StackDataType STTop(ST* ps)
{if (ps-top 0){exit(1);}return ps-a[ps-top - 1];
}void QuickSortNonR(int* a, int left, int right)
{ST s;STInit(s);STPush(s, right);STPush(s, left);while (!STEmpty(s)){int begin STTop(s);STPop(s);int end STTop(s);STPop(s);int pfast begin 1;int pslow begin;int keyi begin;while (pfast end){while (pfast end a[pfast] a[keyi] pslow ! pfast){swap(a[pslow], a[pfast]);}pfast;}swap(a[pslow], a[keyi]);if (pslow 1 end){STPush(s, end);STPush(s, pslow 1);}if (pslow - 1 begin){STPush(s, pslow - 1);STPush(s, begin);}}五、归并排序 归并排序算法思想 归并排序MERGE-SORT是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法DivideandConquer的⼀个⾮常典型的应⽤。将已有序的⼦序列合并得到完全有序的序列即先使每个⼦序列有序再使⼦序列段间有序。若将两个有序表合并成⼀个有序表称为⼆路归并。 1、递归实现 代码实现
//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left right){return;}int mid (right - left) / 2 left;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid 1, right,tmp);//合并int begin1 left, end1 mid;int begin2 mid 1, end2 right;int begin left;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[begin] arr[begin1];}else{tmp[begin] arr[begin2];}}while (begin1 end1){tmp[begin] arr[begin1];}while (begin2 end2){tmp[begin] arr[begin2];}//传值while (left right){arr[left] tmp[left];left;}
}void MergeSort(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp NULL;
}2、非递归实现
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);exit(1);}int k 1;while (k n){int i 0;for (i 0; i n - 2 * k 1;i 2*k){int mid i k - 1;int left i;int right i 2 * k - 1;int begin1 left, end1 mid;int begin2 mid 1, end2 right;int begin left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[begin] a[begin1];}else{tmp[begin] a[begin2];}}while (begin1 end1){tmp[begin] a[begin1];}while (begin2 end2){tmp[begin] a[begin2];}while (left right){a[left] tmp[left];left;}}if (i n-k){int mid ik-1;int left i;int right n-1;int begin1 left, end1 mid;int begin2 mid 1, end2 right;int begin left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[begin] a[begin1];}else{tmp[begin] a[begin2];}}while (begin1 end1){tmp[begin] a[begin1];}while (begin2 end2){tmp[begin] a[begin2];}while (left right){a[left] tmp[left];left;}}k * 2;}free(tmp);
}六、排序算法复杂度及稳定性分析 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前⽽在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 七、计数排序 只能排序整数不适合排不集中的数据如1,10000000,100000002会产生空间浪费 // 计数排序
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 1; i n; i){if (min a[i]){min a[i];}if (max a[i]){max a[i];}}int range max - min 1;int* count (int*)calloc(range ,sizeof(int));for (int i 0; i n; i){count[a[i]-min];}int indext 0;for (int i 0; i range; i){while (count[i]--){a[indext] i min;}}free(count);count NULL;
}
