建立网站 多少钱,wordpress 制作单页,用vs2010做网站应用程序脱机,网页打不开是什么情况八大排序 插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序计算排序 插入排序
基本思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 。 直接插入排序的特性总结直到所有的记录插入完为止得到一个新的有序序列 。 直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
void InsertSort(int* a, int n)
{for (int i 0; i n-1; i){// [0, end] 有序插入tmp依旧有序int end i;int tmp a[i1];while (end 0){if (a[end] tmp){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}希尔排序
基本思想先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算On1.25到O1.6*n1.25稳定性不稳定
void ShellSort(int* a, int n)
{// 1、gap 1 预排序// 2、gap 1 直接插入排序int gap n;while (gap 1){gap gap / 3 1; // 1可以保证最后一次一定是1// gap gap / 2;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}选择排序
基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int maxi begin, mini begin;for (int i begin; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);// 如果maxi和begin重叠修正一下即可if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}堆排序
基本思想利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 直接选择排序的特性总结
堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
//堆排序
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 排升序
void HeapSort(int* a, int n)
{// 建大堆for (int i (n-1-1)/2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}冒泡排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 冒泡排序的特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
void BubbleSort(int* a, int n)
{for (int i 0;i n - 1;i){bool exchange false;for (int j 0;j n - 1 - i;j){if (a[j] a[j 1]){exchange true;Swap(a[j], a[j 1]);}}if (exchange false){break;}}
}快速排序
基本思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
int GetMidIndex(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}
}hoare版本
//右边找比key小左边找比key大交换注意极端情况一次就相遇在keyi或者right最后相遇时交换keyi位置的值和相遇点的值
int PartSort1(int* a, int left, int right)
{int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){// 右边找小while (left right a[right] a[keyi]){--right;}// 左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}挖坑法
//右边找比坑小的值左边找比坑大的值找到了就更新坑的值然后在换坑最后将最开始记录的坑值给最新的坑
int PartSort2(int* a, int left, int right)
{int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int key a[left];int hole left;while (left right){// 右边找小while (left right a[right] key){--right;}a[hole] a[right];hole right;// 左边找大while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}前后指针
//prev为最左开始cur为最左的下一个开始keyi为最左的下标cur找比keyi位置的值小的值找到了就先将perv在交换prev和cur位置上的值cur一直是往后跑当cur走出尾了交换最走的值和prev位置上的值更新新的最左下标
int PartSort3(int* a, int left, int right)
{int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int prev left;int cur left1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}//递归版本快排
void QuickSort(int* a, int begin,int end)
{if (begin end){return;}int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi-1);QuickSort(a, keyi1, end);
}//非递归版本快排
//思想先总统入栈先右后左入栈然后取出来做左右区间每排一次就弹出入新的左右区间注意入栈判断条件
void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);//int keyi PartSort3(a, left, right);int keyi PartSort1(a, left, right);// [left, keyi-1] keyi [keyi1, right]if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}if (left keyi-1){STPush(st, keyi-1);STPush(st, left);}}STDestroy(st);
}归并排序
基本思想建立在归并操作上的一种有效的排序算法将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
//递归版本
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;// 小区间优化/*if (end - begin 1 10){InsertSort(abegin, end - begin 1);return;}*/int mid (begin end) / 2;// [begin, mid] [mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);// 归并两个区间// ...int begin1 begin, end1 mid;int begin2 mid1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(abegin, tmpbegin, sizeof(int) * (end - begin 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
//非递归归并
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);// 1 2 4 ....int gap 1;while (gap n){int j 0;for (int i 0; i n; i 2 * gap){// 每组的合并数据int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;printf([%d,%d][%d,%d]\n, begin1, end1, begin2, end2);if (end1 n || begin2 n){break;}// 修正if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}// 归并一组拷贝一组memcpy(ai, tmpi, sizeof(int)*(end2-i1));}printf(\n);//memcpy(a, tmp, sizeof(int) * n);gap * 2;}free(tmp);
}计算排序
思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中
计数排序的特性总结
计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围)
void CountSort(int* a, int n)
{int min a[0];int max a[0];int i 0;for (int i 0;i n;i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* countA (int*)malloc(sizeof(int) * range);memset(countA, 0, range * sizeof(int));//统计次数for (int i 0;i n;i){countA[a[i] - min];}//排序int k 0;for (int j 0;i range;j){while (countA[j]--){a[k] j min;}}
}
