域名空间做网站,哪些网站是营销型网站及原因,百度关键词排名软件,网页制作报价单目录
引言
一#xff1a;InsertSort(直接插入排序) 二#xff1a;ShellSort(希尔排序) 三#xff1a;BubbleSort(冒泡排序)
四#xff1a; HeapSort(堆排序)
五#xff1a;SelectSort(直接选择排序)
六#xff1a;QuickSort(快速排序) 1.Hoare版本
2.前后指针版本 …目录
引言
一InsertSort(直接插入排序) 二ShellSort(希尔排序) 三BubbleSort(冒泡排序)
四 HeapSort(堆排序)
五SelectSort(直接选择排序)
六QuickSort(快速排序) 1.Hoare版本
2.前后指针版本
3.非递归版本
4.快排之三路划分
5.SGI-IntrospectiveSort(自省排序)
七MergeSort(归并排序)
1.递归版本
2.非递归版本 八CountSort(计数排序) 接下来的日子会顺顺利利万事胜意生活明朗-----------林辞忧
引言
在日常生活当中任何地方都有着排序的思想对于网购时价格排序销量排序好评排序等各种排名因此对于学习排序算法是很重要对于排序算法有常见的八种它们分别是 InsertSort(直接插入排序) ShellSort(希尔排序) BubbleSort(冒泡排序) HeapSort(堆排序) SelectSort(直接选择排序) QuickSort(快速排序) MergeSort(归并排序) CountSort(计数排序) 对于其他的如桶排序奇数排序等实际用处不大很少使用。接下来就介绍这八种排序算法
一InsertSort(直接插入排序)
1.动图 2.思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列
void InsertSort(int* a, int n)
{//[0,end]有序插入a[end1]for (int i 0; i n - 1; i){int endi;int tmp a[end 1];while (end0){if (a[end] tmp){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}
3.时间复杂度O(N^2) 最坏情况是逆序最好情况是有序或者接近有序O(N) 二ShellSort(希尔排序)
1.图片演示 2.思想 先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达 1 时所有记录在统一组内排好序 。 当gap1时为预排序目的是为了接近有序 当gap1时为直接插入排序 间隔为gap的分为一组总共gap组 先对一组进行排序 int gap 3;
for (int i 0; i n - gap; i gap)
{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;
} 再对gap组都进行排序 int gap 3;
for (int j 0; j gap; j)
{for (int i j; i n - gap; i gap){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;}
} 这样就完成了预排序但如果对于数据量大的情况下不止会进行一次预排序且还要控制最后一次预排序的gap1这样就可以直接排序完成 int gap n;
while (gap 1)
{gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){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;}}
} 对于这里可以优化掉一层循环变为 void ShellSort(int* a, int n)
{//当gap1时为预排序目的是为了接近有序//当gap1时为直接插入排序//间隔为gap的分为一组总共gap组int gap n;while (gap 1){gap gap / 3 1;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;}}
} 以前的是一组排序完了再排下一组这里是全部gap组一次排过去 3.关于gap如何取的问题以及一些其他注意问题 时间复杂度O(N^1.3) 三BubbleSort(冒泡排序)
1.动图展示 2. 代码实现
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int exchange 0;for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){Swap(a[j],a[j1]);exchange 1;}}if (exchange 0){break;}}
}
3.时间复杂度O(N^2)
详细介绍可参考https://blog.csdn.net/Miwll/article/details/135315155?spm1001.2014.3001.5501
四 HeapSort(堆排序)
1.图片展示 2.思想及代码实现 堆排序 (Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆 void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[parent] a[child]){Swap(a[parent],a[child]);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){Swap(a[end], a[0]);AdjustDown(a, end, 0);--end;}
}
时间复杂度为O(N*logN)
详细可以参考https://blog.csdn.net/Miwll/article/details/136636869?spm1001.2014.3001.5501
五SelectSort(直接选择排序)
1.动图显示 2.思想及实现 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 void SelectSort(int* a, int n)
{//遍历一遍选出最大和最小值下标再收尾交换int begin 0, end n - 1;int maxi 0, mini 0;while (begin end){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]);if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
}
这里需要注意当begin和maxi重叠的情况 时间复杂度O(N^2)
六QuickSort(快速排序) 1.Hoare版本
1.动图展示 2.思想及实现
对于Hoare版本的快排是选取一个key值然后先让右边先走找小再左边找大再交换继续往后直至相遇再交换key位置处的值再以相遇位置为划分子区间继续执行 画一部分递归展开图理解最小子问题的条件 3.为啥相遇位置一定比key值小---右边先走保证的 4.快排的时间复杂度为O(N*logN),但在有序或者接近有序的情况下最坏为O(N^2),为了防止出现最坏的情况可以使用三数取中或者随机选key来解决问题 //2.三数取中
int mid GetMidi(a,begin, end);
Swap(a[begin], a[mid]);int GetMidi(int*a,int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[right] a[mid])//midleft rightmid{return mid;}else if (a[left] a[right])//midleft rightmid{return left;}else{return right;}}else //leftmid{if (a[right] a[mid])//rightmid{return mid;}else if (a[left] a[right])//rightmid {return right;}else{return left;}}
}
5.小区间优化 由于到最后的几步时递归的深度和广度是非常巨大的因此可以采用小区间优化的方式减少递归这里可以采用插入排序
void QuickSort1(int* a, int begin, int end)
{//最小子问题--区间不存在或者只有一个数据if (begin end) return;//1.随机选key---选[left, right]区间中的随机数做key//int randi rand() % (end - begin 1);//randi begin;//在递归时begin不一定是0开始的//Swap(a[begin],a[randi]);if (end - begin 1 10){InsertSort(abegin, end - begin 1);}else{//2.三数取中int mid GetMidi(a, begin, end);Swap(a[begin], a[mid]);int keyi begin;int left begin, right end;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]);keyi left;//[begin,keyi-1] keyi [keyi1,end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);}
}
2.前后指针版本 1.动图展示 2.思想及实现
当cur处的值key时cur
当cur处的值key时prev,再交换prev和cur的值再cur
void QuickSort2(int* a, int begin, int end)
{if (begin end) return;int prev begin;int cur begin 1;int keyi begin;while (cur end){if (a[cur] a[keyi] prev ! cur){Swap(a[prev],a[cur]);}cur;}Swap(a[prev],a[keyi]);keyi prev;//[begin,keyi-1]keyi[keyi1,end]QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi 1, end);
}
3.非递归版本
对于递归如果深度太深的话就会导致栈溢出因此用栈实现非递归版本很重要
思想走一趟单趟再右左区间入栈
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 left;int cur left 1;int prev left;while (cur right){if (a[cur] a[keyi] prev ! cur)Swap(a[cur],a[prev]);cur;}Swap(a[prev], a[keyi]);keyi prev;//[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);}//Print(a, left, right);}STDestroy(st);
}
4.快排之三路划分
1.快排性能的关键点分析
决定快排性能的关键点是每次单趟排序后key对数组的分割如果每次选key基本⼆分居中那么快 排的递归树就是颗均匀的满⼆叉树性能最佳。但是实践中虽然不可能每次都是⼆分居中但是性能 也还是可控的。但是如果出现每次选到最⼩值/最⼤值划分为0个和N-1的⼦问题时时间复杂度为 O(N^2)数组序列有序时就会出现这样的问题我们前⾯已经⽤三数取中或者随机选key解决了这个问 题也就是说我们解决了绝⼤多数的问题但是现在还是有⼀些场景没解决(数组中有⼤量重复数据时)即以下情况 此时就提出了采用三路划分的思想来解决 这样再对比key大的数据区间和比key小的数据区间进行递归
//三路划分
void QuickSort3(int* a, int begin, int end)
{//最小子问题if (begin end) return;int left begin, right end;int key a[left];int cur left 1;while (cur right){if (a[cur] key){Swap(a[left], a[cur]);cur;left;}else if(a[cur]key){Swap(a[cur],a[right]);--right;}else{cur;}}//[begin,left-1][left,right][right1,end]QuickSort3(a, begin, left - 1);QuickSort3(a, right1, end);
}
5.SGI-IntrospectiveSort(自省排序) introsort是introspectivesort采⽤了缩写他的名字其实表达了他的实现思路他的思路就是进⾏⾃ 我侦测和反省快排递归深度太深sgistl中使⽤的是深度为2倍排序元素数量的对数值那就说明在 这种数据序列下选key出现了问题性能在快速退化那么就不要再进⾏快排分割递归了改换为堆 排序进⾏排序
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left right)return;// 数组长度⼩于16的⼩数组换为插入排序简单递归次数---小区间优化 if (right - left 1 16){InsertSort(a left, right - left 1);return;}// 当深度超过2 * logN时改用堆排序 if (depth defaultDepth){HeapSort(a left, right - left 1);return;}depth;int begin left;int end right;// 随机选keyint randi left (rand() % (right - left));Swap(a[left], a[randi]);int prev left;int cur prev 1;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;// [begin, keyi-1] keyi [keyi1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi 1, end, depth, defaultDepth);
}void QuickSort4(int* a, int begin, int end)
{int depth 0;int logn 0;int N end - begin 1;for (int i 1; i N; i * 2){logn;}// introspective sort -- 自省排序IntroSort(a, begin, end, depth, logn * 2);
}
七MergeSort(归并排序)
1.递归版本
1.动图演示 2.思想及实现 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有 序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并 void _MergeSort(int* a, int left,int right,int*tmp)
{//最小子问题if (left right) return;int mid (left right) / 2;//[begin,mid][mid1,end]_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);//开始归并int begin1 left, end1mid;int begin2mid1, end2right;int i left;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(a left, tmp left, sizeof(int) * (right-left1));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail\n);return;}_MergeSort(a, 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\n);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 begin1 gap - 1;int begin2 end1 1, end2 begin2 gap - 1;//调整越界问题if (end1 n || begin2 n){break;}if (end2 n)//修正{end2 n - 1;}int j i;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(a i, tmp i, sizeof(int) * (end2-i1));}gap * 2;}
} 八CountSort(计数排序)
1.思想及实现
开辟一个数组用来统计每个数据出现的次数在相对映射位置的次数然后再往原数组写入数据适合于整形且数据集中的
void CountSort(int* a, int n)
{int min a[0];int 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*)malloc(sizeof(int) * range);if (count NULL){perror(malloc fail\n);return;}memset(count, 0, sizeof(int) * range);//统计次数for (int i 0; i n; i){count[a[i] - min];}//写回原数组int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}
} 总结
