轻松搞定十大排序算法(c++版)
CSDN:https://blog.csdn.net/opooc
0、简介
本文章，是为了让读者会用十大排序算法。如果您对本文感兴趣，欢迎关注我☺。如对本文章有任何的疑问或者您有更好理解，欢迎在评论区写下您的见解。
1、相关概念
时间复杂度：
反映当数据量变化时，操作次数的多少;时间复杂度在评估时，要只保留最高项，并且不要最高项的系数。(下面用logN表示 log以2为底，N的对数)
空间复杂度：
是指算法在计算机内执行时，所需额外开辟的空间。
指标：
同时间复杂度。
常数项：
与N的大小无关的操作。
稳定性：
(1)稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
(2)不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
2、算法分类
十大经典排序算法可以分为两大类：
0、非线性时间排序：通过比较来决定元素间的相对次序。时间复杂度最快为O(logN)
1、线性时间排序：通过创建有序的空间，将元素按照一定的规则放入有序空间，再依次取出。以空间来换取时间，可以突破O(logN)
-
非线性时间排序
-
比较排序
- 冒泡排序
- 快速排序
-
插入排序
- 插入排序
- 希尔排序
-
选择排序
- 选择排序
- 堆排序
-
归并排序
- 二路归并排序
- 多路归并排序
-
比较排序
-
线性时间排序
- 计数排序
- 堆排序
- 基数排序
3、各算法的时间复杂度
| 排序算法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O($N^2$) | O($N^2$) | O($N^2$) | O($1$) | 稳定 |
| 冒泡排序(外层优化) | O($N^2$) | O($N^2$) | O($N$) | O($1$) | 稳定 |
| 冒泡排序(外+内优化) | O($N^2$) | O($N^2$) | O($N$) | O($1$) | 稳定 |
| 快速排序(经典) | O($NlogN$) | O($N^2$) | O($NlogN$) | O($logN$) | 不稳定 |
| 快速排序(随机) | O($NlogN$) | O($NlogN$) | O($NlogN$) | O($logN$) | 不稳定 |
| 插入排序 | O($N^2$) | O($N^2$) | O($N$) | O($1$) | 稳定 |
| 希尔排序 | O($N^1.3$) | O($N^2$) | O($N$) | O($1$) | 稳定 |
| 选择排序 | O($N^2$) | O($N^2$) | O($N^2$) | O($1$) | 稳定 |
| 堆排序 | O($NlogN$) | O($NlogN$) | O($NlogN$) | O($1$) | 不稳定 |
| 二路归并排序 | O($NlogN$) | O($NlogN$) | O($NlogN$) | O($N$) | 稳定 |
| 多路路归并排序 | O($NlogN$) | O($NlogN$) | O($NlogN$) | O($N$) | 稳定 |
| 计数排序 | O($N+k$) | O($N+k$) | O($N+k$) | O($N+k$) | 稳定 |
| 桶排序 | O($N+k$) | O($N^2$) | O($N+k$) | O($N+k$) | 稳定 |
| 基数排序 | O($N*k$) | O($N*k$) | O($N*k$) | O($N+k$) | 稳定 |
4、排序算法的实现
0、通用函数及其他
(1)、求数组长度（需要传数组，不要传数组指针）
/* 这里的注意点：在计算数组大小的时候，
一定要注意传入的数组是否为数组指针，
如果传入的是数组指针，sizeof后出来的值为8(64位下)，读者应注意。
*/
template <class T>
int len(T& arr){
int length = (int)sizeof(arr)/sizeof(arr[0]);
return length;
}
(2)、交换数组两个数
void exchangee(int arr[],int a, int b){
/* ^符号 即”异或“运算符，特点是与0异或，
保持原值；与本身异或，结果为0。
这里可以使用位运算，交换时不用开辟额外空间。
但是如果传入的'位置相同'的两个数，就不能在此函数中进行交
换。因为，自己跟自己异或后结果一定为0,就没有什么意义了。
// arr[a] = arr[a] ^ arr[b];
// arr[b] = arr[a] ^ arr[b];
// arr[a] = arr[a] ^ arr[b];
*/
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
(3)、算法中的表达
* A代表平均时间复杂度 * B代表最坏时间复杂度 * E代表最好时间复杂度 * 省略了O()
(3)、大数据样本下四钟最快算法的比较
/*
数据是随机整数，时间单位是秒
数据规模|快速排序 归并排序 希尔排序 堆排序
1000万 | 0.75 1.22 1.77 3.57
5000万 | 3.78 6.29 9.48 26.54
1亿 | 7.65 13.06 18.79 61.31
*/
(4)、时间复杂度的大小比较
/*
N!> x^N >...>3^N >2^N > N^x>...>N^3 >N^2>NlogN>N>logN>1
*/
(5)数组和数组大小的结构体
struct arrAndSize{
int *array;
int size;
};
(6)初始化数组
//一维 每个元素都没有初始化
int *p = new int[10];
//一维 每个元素初始化为0
int *p = new int[10](0);
//二维 每个元素都没有初始化
int (*bucket)[10] = new int[10][10];
//二维 每个一维中含N个数，N为确定的数值。
vector<vector<int>> bucket(N);
//通过动态创建的数组，要进行内存释放，否则内存将泄漏
//(本文中，未进行内存释放)
delete []p;
(7)综合排序总结
- 思考一个排序时候，考虑时间复杂度中的指标和常数项，空间复杂度，稳定性.
- 代码规模，一定程度上说明了常数项的大小。（最终常数项的大小是看发生常数操作的次数）
- 系统的sort 方法，发现传进来的值为数值型，会使用快排，如果发现传的还有比较器，会使用归并排序
-
归并和快排哪种更快？
快排比归并排序的常数项要低，所以要快。 -
为什么会有归并和快排两种呢？
在比较的时候，使用比较器的时候，要追求一个稳定性，使用 归并排序 可以达稳定性的效果；使用快排不能够实现稳定性的效果。 - 面对大规模的时候，当排序量是小于等于60的时候，sort方法 会在内部使用插入排序的方法（不一定是60，是一定的规模）当数据量很低的时候，插入排序的常数项低。
-
在c语言中有一版，把归并排序，改成非递归，是基于工程其他考虑。
*/
(8)对比两个数组是否相同
bool isEqual(int firstArr[],int Second[]){
if ((firstArr == nullptr && Second != nullptr) ||(firstArr != nullptr && Second == nullptr)) {
return false;
}
if (firstArr == nullptr && Second == nullptr) {
return true;
}
if (len(firstArr) != len(Second)) {
return false;
}
for (int i = 0; i< len(firstArr); i++) {
if (firstArr[i] != Second[i]) {
//可以在此位置，打印错误项
//也可以打印整个数组查看错误项
return false;
}
}
return true;
}
(9)复制数组
int* arrayCopy(int oldArray[],int length){
if (oldArray == nullptr) {
return nullptr;
}
int* newArray = new int[length];
for (int i = 0; i<length;i++) {
newArray[i] = oldArray[i];
}
return newArray;
}
(10)产生随机数组
arrAndSize generateRandomArr(int maxSize,int maxValue){
// int arrrr =rand()%10;
arrAndSize aAndS;
int size = (int)((maxSize+1) * (rand()%10/(double)10));
cout<<"{"<<size<<"}";
int* array = new int[size];
for(int i =0 ;i < size;i++){
// 随机生成[-N,N];
// array[i] = (int)((maxValue +1) * (rand()%100)/(double)100) - (int)((maxValue + 1) * (rand()%100/(double)100));
//随机生成[0,N];
array[i] = (int)((maxValue +1) * (rand()%10)/(double)10);
//打印到底生成了什么。
//cout<<i<<"===="<<array[i] <<"|";
}
// cout<<"+++++"<<endl;
aAndS.size = size;
aAndS.array = array;
return aAndS;
}
(11)疯狂递归 -递归master公式
/*
递归master公式
T(N)的公式从大规模来看，不细分。
T(N) = a * T(N/b)+O(n^d)
N/b 是子过程数据量 ；a是子过程调用多少次；O(n^d)是出去
过程之外剩下的数据量的多少
if log(b)a > d => O(N^log(b)a)
if log(b)a = d => O(N^d *logN)
if log(b)a < d => O(N^d)
注意 多个递归的规模必须一样，否则master公式失效。
例如一个规模是1/3;一个是2/3;
以下算法的时间复杂度：a = 2;b = 2;d = 0;所以时间复杂度为O(N)
*/
int process(int arr[] ,int L,int R){
if (L == R) {//base case;
return arr[L];
}
int mid = (L+R)/2;
int LeftMax = process(arr, L, mid);
int RightMax = process(arr, mid+1 , R);
return (LeftMax /RightMax)?LeftMax : RightMax;
}
int getMaxInArray(int arr[],int length){
return process(arr , 0 , length-1);
}
(12)比较器
/*
按照年龄降序比较器
比较器使用的时候 不和java一样，c++中的比较器要注意返回值要为bool类型，
而java中的返回值可以为int类型，根据两数相减进行判断下一步的排序。
比较器第一次比较完成后，下一次在比较的时候还是会含有第一次的排号的顺序，
是利用了c++中sort函数的排序稳定性.
*/
//比较器的结构体
struct student{
char name[10];
int age;
int classId;
};
//按照年龄升序比较器
bool compareSmallAge(student s1,student s2){
//这里返回false的时候，相当于进行了一个交换操作
return s2.age > s1.age;
}
//按照班级升序比较器
bool compareSmallClassId(student s1, student s2){
return s2.classId > s1.classId;
}
void testComparator(){
student s1 = {"opooc",21,100};
student s2 = {"cat",30,105};
student s3 = {"dog",1,107};
student s4 = {"daolao",2,107};
student s5 = {"dst",20,103};
student allStudent[] ={s1,s2,s3,s4,s5};
sort(allStudent, allStudent+5, compareSmallAge);
//上面按照年龄升序后的结果，会继续在下面的班级降序中体现出来
sort(allStudent, allStudent+5, compareSmallClassId);
}
(13)vector容器
//声明一个一维容器
vector<int> v;
//声明一个二维数组，里面每个一维数组大小为10(必填)
vector<vector<int>> v1[10];
//添加元素
v.push_back(1);
//删除最后添加的元素
v.pop_back();
//删除向量中迭代器指向元素
v.erase(v.begin()+1);
//删除向量中[first,last)中元素 如下删除1234位置
v.erase(v.begin()+1,v.begin()+5);
//在第零个元素前面插1
v.insert(v.begin(),1);
//在第二个元素前插2
v.insert(v.begin()+2,2);
//在最后一个元素后面插的10
v.insert(v.end(),10);
//元素的个数
v.size();
//清除所有元素
v.clear();
//遍历整个数组
vector<int>:: iterator it;
for (it = v.begin(); it != v.end(); it++) {
cout<< *it;
}
1、冒泡排序
算法描述:
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
动画演示:
实现逻辑:
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
1.0、简单冒泡排序
（交换排序;时间A:N^2 ,B:N^2 ,E:N^2 ;空间1;稳定）
for (int i = 1 ; i<length; i++) {
for (int j = 0 ; j<length - i; j++) {
if(arr[j]>arr[j+1]){
exchangee(arr, j, j+1);
}
}
}
1.1、外层循环优化冒泡排序
(交换排序; 时间A:N^2 , B:N^2 , E:N; 空间1; 稳定)
/*
如果用一个flag来判断一下，当前数组是否已经有序,
有序就退出循环，可以提高冒泡排序的性能。
*/
for (int i = 1; i<length; i++) {
bool flag = true;
for (int j = 0; j < length -i; j++) {
if (arr[j]>arr[j+1]) {
exchangee(arr, j, j+1);
flag =false;
}
}
if (flag) {
break;
}
}
1.2、内层循环优化冒泡排序
(交换排序; 时间A:N^2 , B:N^2 , E:N ; 空间1 ; 稳定）
/*
(1)完美冒泡
(2)再用last标记一下最后一个发生交换的数，
下次可以减少循环次数。其中第一次内部循环的控制条件，单独拿出来。
*/
2、快速排序
算法描述:
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
动画演示:
实现逻辑:
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法流程如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2.0、随机快速排序
（交换排序;时间A:NlogN,B:NlogN,E:NlogN;空间logN;不稳定）
/*
(1)in-place原地算法可以实现 把以划分值为标准，
小于等于划分值的放左边并推着大于划分值的数向右走。
时间复杂度O(N)空间复杂度是O（1）
(2)（荷兰国旗问题）在实现把等于划分值的放中间，小于
划分值的放左边，大于划分值的放右边且时间复杂度O(N)
空间复杂度仍未O(1)的时候。1.当前数<p左区下一个
交换，左区扩，检测下一个。2、当前数等于p，检测下
一个。3、当前数大于p，和右区前一个位置换，右区扩。
继续检测当前换完的数。
(3) 其中的空间复杂度是不得不使用的空间，用来记录每次的左右边界。
(4)快速排序可以做到稳定，但是非常难，可以搜 0-1stable sort论文。
*/
int* separate(int arr[],int left,int right){
int first = left -1;
int Second = right;
while (left < Second) {
if(arr[left]<arr[right]){
exchangee(arr, ++first, left++);
}else if(arr[left]>arr[right]){
exchangee(arr, --Second, left);
}else if(arr[left]==arr[right]){
left++;
}
}
exchangee(arr, Second, right);
int firstAndSecond[2] = {first+1,Second};
return firstAndSecond;
}
void quickSort(int arr[],int left, int right){
if (left<right) {
int randomC = (int)((rand()%100/(double)100) * (right - left +1));
exchangee(arr,left+ randomC, right);
int* curArr = separate(arr, left, right);
quickSort(arr, left,curArr[0] -1 );
quickSort(arr, curArr[1]+1, right);
}
}
void quickSort(int arr[],int length){
if (length < 2) {
return;
}
quickSort(arr,0,length-1);
}
int main(){
int arr[9]={99,11,72,62,53,4,44,21,14};
int length = len(arr);
quickSort(arr,length);
return 0;
}
2.1、小和问题
问题描述
求小和问题：在随机元素，随机数组大小的数组中，找出左边比右边元素小的所有元素之和。
例如：数组[4,2,5,1,7,3,6] 第一个元素4比2大，不算小和，5比4和2都大，那就是4+2=6；1比4和2和5都小，不算小和；7比前面的都大，那就是上次小和6+4+2+5+1=18；然后3前面比2和1大，那就是18+2+1=21；最后6比4、2、5、1、3都大，结果就是21+4+2+5+1+3=36。那么最后的结果就是36。
//小和问题
int allSum(int arr[],int L,int mid,int R){
int *help = new int(R-L+1);
int i = 0 ;
int pFirst = L;
int pSecond = mid + 1;
int sum = 0;
while (pFirst <=mid && pSecond <=R) {
/*
在左右两个区有谁小谁移动的原则
看小和问题和逆序对问题时，要抓住一边分析。
（小和问题，因为要统计左区小于右区的数的数量，
既统计左区比右区小的数，因为在排序的时候，左区可能会移动，
故左区在移动后，无法在下一步查看右区大于的数，
所以要一次性把针对左区当前数大的数全部记录下来
逆序对问题，则需要一个一个记录左区比右区大的数。）
*/
sum += arr[pFirst] < arr[pSecond] ? arr[pFirst]*(R-pSecond+1):0;
help[i++] = arr[pFirst] < arr[pSecond] ? arr[pFirst++]:arr[pSecond++];
}
while (pFirst <= mid ) {
help[i++] = arr[pFirst++];
}
while (pSecond <= R) {
help[i++] = arr[pSecond++];
}
for (int k = 0; k < (R-L+1); k++) {
arr[L+k] = help[k];
}
return sum;
}
int smallSum(int arr[],int L,int R){
if (L==R) {
return 0;
}
int mid = L+((R-L)>>1);
// 相当于 int mid = L+(R-L)/2;
int leftSum = smallSum(arr, L, mid);
int rightSum = smallSum(arr, mid + 1, R);
int leftAndRightSum = allSum(arr,L,mid,R);
return leftSum + rightSum + leftAndRightSum;
// return smallSum(arr, L, mid)+smallSum(arr, mid + 1, R)+allSum(arr,L,mid,R);
}
int smallSum (int arr[],int length){
if(arr == nullptr || length <2){
return 0;
}
return smallSum(arr,0,length -1);
}
3.0、插入排序
算法描述:
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
动画演示:
实现逻辑:
一般来说，插入排序都采用in-place在数组上实现。具体算法流程如下：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
3.0、插入排序
(插入排序;时间A:N^2 , B:N^2 , E:N;空间1;稳定)
//方法一、在对比的时候不交换；
for (int i =1; i < length;i++ ) {
int current = arr[i];
int preIndex = i-1;
while (preIndex >= 0&& arr[preIndex]>current) {
/*
可以直接交换。因为current记录了最后一个值，
所以这里使用向后移动思想。
exchangee(arr, preIndex, current);
*/
arr[preIndex+1] = arr[preIndex];
preIndex --;
}
arr[preIndex+1] = current;
}
//方法二、在对比的时候进行交换；
for(int i = 1 ; i<length ;i++){
for (int j = i - 1; j>=0 && arr[j]>arr[j+1]; j--) {
exchangee(arr, j, j+1);
}
}
4、希尔排序
算法描述:
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
动画演示:
实现逻辑:
>
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法流程：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.0、希尔排序
(插入排序;时间A:N^1.3 , B:N^2 , E:N;空间1;不稳定)
/*
(又称缩小增量排序)
通过实验，大量本表现出，平均时间复杂度为N^1.3
*/
int gap = length;
while (gap>1){
gap = gap/3 +1;
for (int i = gap; i<length; i+=gap) {
int current = arr[i];
int preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex]>current) {
arr[i] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex+gap] = current;
}
}
5、选择排序
算法描述:
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
动画演示:
实现逻辑:
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法流程如下：
初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
5.0、选择排序
(选择排序;时间A:N^2 , B:N^2 , E:N^2 ; 空间1;稳定)
for(int i =0 ;i<length-1;i++)
{ int minIndex =i;
for(int j= i+1;j<length;j++){
if(arr[minIndex]>arr[j]){
minIndex = j;
}
}
exchangee(arr, minIndex, i);
}
6、堆排序
算法描述:
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
动画演示:
实现逻辑:
>
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
6.0、堆排序
(选择排序;时间A:NlogN,B:NlogN,E:NlogN;空间1;不稳定)
/*
堆的概念：对于大根堆，其子树下的所有节点，
包括它自己在内的最大值为头结点。
时间复杂度为0+log1+log2+……数学上可以证明
这个值收敛于O(N)
*/
//向上走
void heapInsert(int arr[],int index){
while (arr[index] > arr[(index-1)/2]) {
exchangee(arr,index, (index-1)/2);
index = (index -1)/2;
}
}
//向下走
//size为最右的边界，size是取不到的.
void heapify(int arr[],int index ,int size){
int leftChild = index*2 + 1;
while (leftChild < size) {
int maxChild = leftChild + 1 < size && arr[leftChild+1] >arr[leftChild] ? leftChild+1 : leftChild;
int maxAll = arr[maxChild] > arr[index] ? maxChild: index;
if (maxAll == index) {
break;
}
exchangee(arr, maxAll, index);
index = maxAll;
leftChild = index*2 +1;
}
}
int main(){
for(int i = 0;i <length;i++){
heapInsert(arr, i);
}
int size = length;
exchangee(arr, 0, --size);
while (size > 0){
//heapify时间复杂度为O(logN)
heapify(arr, 0, size);
exchangee(arr, 0, --size);
}
return 0;
}
7、归并排序
算法描述:
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
动画演示:
实现逻辑:
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
7.0、二路归并排序
(插入排序;时间A:NlogN,B:NlogN,E:N*logN;空间N;稳定)
/*
归并排序内部缓存法 可以把空间复杂度降到O(1)；
归并排序原地归并法 也可以把空间复杂度降到O(1)但是时间复
杂度会变成O(N^2)
*/
void merge(int arr[],int L,int M,int R){
int* cent = new int[R - L + 1];
int i = 0;
int pFirst = L;
int pSecond = M+1;
while (pFirst <= M && pSecond <= R) {
cent[i++] = arr[pFirst] < arr[pSecond] ? arr[pFirst++]:arr[pSecond++];
}
while (pFirst <= M) {
cent[i++] = arr[pFirst++];
}
while (pSecond <= R) {
cent[i++] = arr[pSecond++];
}
for (int j = 0; j < (R-L+1); j++) {
arr[L+j] = cent[j];
}
}
void mergeSort(int arr[],int L,int R){
if (L == R){
return;
}
int mid = (L+R)/2;
mergeSort(arr, L, mid);
mergeSort(arr, mid+1, R);
merge(arr,L,mid,R);
}
void mergeSort(int array[],int length){
if (array == nullptr || length<2) {
return;
}
mergeSort(array,0,length - 1);
}
8、计数排序
算法描述:
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
动画演示:
实现逻辑:
>
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加(从桶中的第0个元素开始，每一项和前一项相加);
反向填充目标数组：将每个元素i放在新数组的第C(i)项,
每放一个元素就将C(i)减去1，是为了保证算法的稳定性。
8.0、计数排序
(计数排序;时间A:N+k,B:N+k,E:N+k;空间N+k;稳定)
/* 输入的元素是 n 个 0到 k 之间的整数
当k不是很大并且序列比较集中时，计数排序是一个很有效的
排序算法。
下面算法是输入的数组中的最小值大于等于0的情况，
可以根据需求更改。
*/
void countSort(int arr[] ,int length){
int max = arr[0];
int lastIndex= 0;
for (int i = 1; i<length; i++) {
max = arr[i]>max ? arr[i]:max;
}
int* sortArr = new int[max+1]();
for (int j = 0; j< length; j++) {
sortArr[arr[j]]++;
}
for (int k = 0; k<max+1; k++) {
while (sortArr[k]>0) {
arr[lastIndex++] = k;
sortArr[k]--;
}
}
}
9、桶排序
算法描述:
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
图片演示:
实现逻辑:
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
9.0、桶排序
桶排序(时间A:N+k,B:N^2,E:N+k;空间N+k;稳定)
//桶排序是: 桶思想排序 + 一个普通的排序（常用快速排序）
#pragma mark bucketSort
/*
映射函数getGroupCount是得到在第几个桶，其能保证第一
个桶有整个数组的最小值和最后一个桶有整个数组的最大值。
*/
int getGroupCount(long num,long size ,long min ,long max ){
int count = (int)((size)*(num - min)/(max - min));
return count;
}
//size 为一个桶的囊括的数的范围
void bucketSort(int arr[],int length,int size){
if (length < 2 ){
return;
}
int len = length;
//拿到最大最小值
long min = arr[0];
long max = arr[0];
for (int i = 1 ; i<len; i++) {
min = arr[i] < min ? arr[i]: min;
max = arr[i] > max ? arr[i]: max;
}
//如果最小值等于最大值说明数组中就一种数
if (min == max) {
return;
}
//创建桶
int bucketCount = (int)((max -min)/size +1);
vector<vector<int>> bucket(bucketCount);
int bid = 0;
//把数组中的数 扔进桶里
for (int i =0; i < len; i++) {
bid = getGroupCount(arr[i], bucketCount, min, max);
bucket[bid].push_back(arr[i]);
}
for (int i=0; i< bucketCount; i++) {
//对桶内进行插入排序。按照升序，这样可以保证从下往上读的稳定性
for (int j = 1; j<bucket[i].size(); j++) {
if (bucket[i][j] < bucket[i][j-1]) {
swap(bucket[i][j],bucket[i][j-1]);
}
}
for (int t = 0; t< bucket[i].size(); t++) {
cout<<bucket[i][t]<<' ';
}
}
// int *newArr = new int[len];
int index = 0;
for (int i =0 ;i<bucketCount ;i++){
for (int j =0; j<bucket[i].size(); j++) {
arr[index++] = bucket[i][j];
}
}
}
9.1、桶排序思想
问题描述
数组最大值问题。
给定一个无序数组，求如果排序之后，相邻两数的最大差值，
要求时间复杂度O（N），且要求不能用基于比较的排序。
以此题发现桶排序妙趣思想.
/*
映射函数getGroupCount是得到在第几个桶，其能保证第一
个桶有整个数组的最小值和最后一个桶有整个数组的最大值。
*/
int getGroupCount(long num,long size ,long min ,long max ){
int count = (int)((size-1)*(num - min)/(max - min));
return count;
}
int maxGroup(int arr[],int length){
if (length < 2){
return 0;
}
int len = length;
//拿到系统的最大值和系统的最小值
int min = INT_MAX;
int max = INT_MIN;
for (int i= 0; i<len; i++) {
min = arr[i]<min ? arr[i]:min;
max = arr[i]>max ? arr[i]:max;
}
if (min == max){
return 0;
}
int bid = 0;
int* maxValue =new int[len+1];
int* minValue =new int[len+1];
bool* flag = new bool[len+1];
for (int j = 0; j<len; j++) {
bid = getGroupCount(arr[j], len, min, max);
minValue[bid] = minValue[bid]? (minValue[bid]<arr[j]?minValue[bid]:arr[j]):arr[j];
maxValue[bid] = maxValue[bid]? (maxValue[bid]>arr[j]?maxValue[bid]:arr[j]):arr[j];
flag[bid] = true;
}
int res = 0;
int lastMax = 0;
for (int k= 1 ; k<len+1; k++) {
if (flag[k]) {
res = res > (minValue[k] - maxValue[lastMax]) ? res :(minValue[k] - maxValue[lastMax]);
lastMax =k;
}
}
return res;
}
10、基数排序
算法描述:
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
动画演示:
实现逻辑:
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
10.0、基数排序
(基数排序;时间A:N k , B:N k , E:N * k ; 空间N+k ; 稳定)
//拿到传入数的位数
int getRadixCount(int count){
int num = 1;
if (count /10 >0) {
num ++;
}
return num;
}
//拿到10的传入位数的次方(10^num)
int getTenRadixCount(int radixCount){
int tenRadix = 1;
while (radixCount > 0 ) {
tenRadix *= 10;
radixCount --;
}
return tenRadix;
}
void radixSort(int arr[], int length){
int len = length;
int max = arr[0];
for (int i =1 ; i< length; i++) {
max = arr[i]>max? arr[i]:max;
}
int radixCount = getRadixCount(max);
int tenRadixCount = getTenRadixCount(radixCount);
int (*bucket)[10] = new int[10][10];
int* num = new int[10]();
int multiplier = 1;
while (multiplier < tenRadixCount) {
for (int i = 0; i< len; i++) {
int curCount = arr[i]/multiplier%10;
int k = num[curCount];
bucket[curCount][k] = arr[i];
num[curCount]++;
}
int index = 0;
for (int j = 0; j < 10; j++) {
if (num[j]!=0) {
for (int k =0; k<num[j]; k++) {
arr[index++] = bucket[j][k];
}
}
//把桶清空，准备下一次循环。
num[j] = 0;
}
multiplier *= 10;
}
}
