一.8种排序方式总览分析(带图)
1.按方式分类(比较排序)
*计数排序:非比较排序
二.8种排序方式详细解析
1.计数排序
注意:计数排序适合范围集中,且范围不大的整型数组排序。不适合范围分散或者非整型的排序,如:字符串、浮点数 等
步骤:
1.找到原数组最大的值,记作range
2.设置一个计数数组,遍历一遍原数组O(n),统计每个数据出现的次数。
3.遍历一遍计数数组O(range)
计数排序分为:相对映射型和非相对映射型(相对位置)
图示意:
2.冒泡排序
遍历有序区间的各个数,从其开始到结尾的区间内轮转交换,不断缩小区间。
原理:不断把大/小的数移到后面
注意点:为提高效率,当发现一次循环中没有数对交换,即可中止循环。
void BubbleSort(int*a,int n) { int i = 0,j=0; for (j = 0; j<n; j++) { bool exchange = false; for (i = 0; i < n-j; i++) { if (a[i + 1] < a[i]) { Swap(&a[i + 1], &a[i]); exchange = true; } } //加入判断环节,提前终止,提高效率 if (exchange == false) { break; } } }
3.选择排序
遍历有序区间的各个数,找出其之后的最大/最小数并与该数之后的数进行替换。
代码的设计思路是设置left,right下标从数组两端向中间遍历,依次筛选出最大值和最小值mini,maxi,并分别与left,riight进行交换。
注意点:在交换过程中,left所处的位置可能正好被maxi标记,接下来下一步maxi与right的交换则会出错,right无法与正确的maxi交换。
解决方法:如果left和maxi重叠,交换后要修正
void SelectSort(int* a, int n) { int left = 0; int right = n; while (left < right) { int mini = left, maxi = right; for (int i =left+1; i <= right; i++) { if (a[i] > a[maxi]) { maxi = i;//移动下标 } if (a[i] < a[mini]) { mini = i; } } Swap(&a[left], &a[mini]); if (left == maxi) { maxi = mini; } Swap(&a[right], &a[maxi]); left++; right--; } }
4.插入排序
遍历有序区间的各个数,把其视作临时变量tmp,分别于它前面的数进行对比,
其进一步优化即为“希尔排序”
注意点:此算法中,当tmp比第一个数大/小时,end会到-1的位置。所以采用图中标记用法。
//升序 void InsertSort(int* a, int n)//a 数组 n 个数 { int i = 0; for (i = 1; i < n; i++) { int end = i - 1; int tmp = i; while (end >= 0) { if (a[tmp] < a[end]) { //整体后移 a[end + 1] = a[end]; --end; } else { break; } } //填空 a[end + 1] = a[tmp]; } }
5.希尔排序
其可以理解为在插入排序的基础上进行预排序(分组插排)
注意点:图示辅助理解循环:
void ShellSort(int* a, int n) { //gap==1 插入排序 //gap>1预先排序 int gap=n; //升序 while(gap>1) { gap = gap / 2; //gap=gap/3+1 确保gap的跳跃到最后为1, int i = 0; for (i = 0; i < n-gap; i++) { int end = i; int tmp = i+gap; while (end >= 0) { if (a[tmp] < a[end]) { //整体后移 a[end + gap] = a[end]; end -= gap; } else { break; } } //填空 a[end + gap] = a[tmp]; } } }
6.堆排序
详情可见博主关于堆排详解:
7.快速排序(递归和非递归写法)
任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中的所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
注意点:当快速排序接近二分(二叉树)的递归模式时,效率最高。因此引入“三数取中”优化代码:
int GetMidNumi(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 left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } }
1.三种排序方式
1.交换法
1.左边做key,右边先走——保证相遇位置比key小
ps:【右边先走找比key小的数,则其停止位置一定小于等于key】
2.由于左右相遇的位置一定比key小,把左边与相遇位置替换
图示:
代码:
2.挖坑法
1.先将左边第一个数据放在临时变量key中,原地形成一个坑位
2.右边先动,找小于key的数,放到坑位中,并且原地新生成一个坑位
3.当左右相遇时,将key填入最后一个坑位中
3.前后指针法(玩区间)
1.左边第一个数设为key,prev(延迟指针),cur(实时指针)
2.cur开始向右移动,找到比key小的值prev和cur同时移动
3.找到比key大的值只移动cur——保证prev和cur中间隔着一段比key大的区间
4.找到比key小的值时,交换prev下一个位置(比key大的区间)和cur位置的值——比key大的值翻到区间右边,把比key小的值翻到区间左边。
图示: