排序算法的实现（插入，希尔，选择，冒泡，堆排，快排）

目录

1.选择排序

2.冒泡排序

3.堆排序

4.插入排序

5.希尔排序

6.快排

6.1快排的优化

6.2快排（双指针法）

6.3快排（非递归）

7.归并排序

7.1归并非递归

8.计数排序

---

1.选择排序

对n个元素进行选择排序，我们可以遍历一轮找出最大值放在末尾，直到循环n-1次。

为了提高效率，我们可以同时找出最大值和最小值，分别放在末尾和开头。

//选择排序
void SelsectSort(int* a,int n)
{int begin=0,end=n-1;//begin要参与排序元素的第一个 end参与排序元素的最后一个 while(begin<end){int maxi=begin,mini=begin,i;//maxi记录最大值下标 mini记录最小值的下标 for(i=begin;i<=end;i++){if(a[maxi]<a[i]) maxi=i;if(a[mini]>a[i]) mini=i;}Swape(&a[maxi],&a[end]);//最大值放最后面 if(mini==end) mini=maxi;//如果最后面正好是最小值 那最小值会跑到下标为maxi上 Swape(&a[mini],&a[begin]);//最小值放最前面 begin++;//把已经排好的退出循环 end--;}
}

2.冒泡排序

左边和右边比较，大于就交换。每循环一趟最大值都会出现在最右边。

//冒泡排序
void BubbleSort(int* a,int n)
{int i,j;for(i=0;i<n-1;i++)//循环趟数 {for(j=0;j<n-1-i;j++)//-i减去排好的 {if(a[j]>a[j+1]) Swape(&a[j],&a[j+1]); }}
}

3.堆排序

要实现堆排序，我们先要用向下调整对数组建立堆结构。(向下调整比向上调整效率高)

实现升序就建大堆，堆顶为最大值，堆顶与最后一个元素交换，然后把最后一个元素(也就是最大值)剔除，再进行建堆。一直循环直到只剩堆顶元素。

同样降序就建小堆。

//向下调整(大堆) 根节点下标0
void AdjustDown(HPDataType*a,int n,int parent)//n为元素个数，最后一个元素下标为n-1 
{   int child=parent*2+1;//找当前父母孩子 while(child<n){if(child+1<n&&a[child]<a[child+1]) child++;//找最大的孩子 if(a[parent]<a[child])//大的值向上调 {change(&a[parent],&a[child]); }else break;//父母节点>=孩子节点 符合堆结构 不用继续向下调整parent=child;//继续向下进入下一层循环 child=parent*2+1;}
} 

// 对数组进行堆排序(升) 
void HeapSort(int* a, int n)
{   int i;for(i=(n-1-1)/2;i>=0;i--)//n-1最后一位元素下标 （n-1-1）/2找最后一位结点的父母下标 {                          AdjustDown(a,n,i);//向下交换 建堆 }int end=n-1;//end最后一个元素下标 while(end>0){change(&a[0],&a[end]);//最大元素与最后一个元素交换 AdjustDown(a,end,0);//向下交换找出最大值 时间复杂度logn (因为end传过去是被当作元素个数来看待，最后一个元素不会参与堆的再构建)end--;//最后一个元素排完，--脱离堆结构 }//循环再找次大 并排到堆结构的最后一位 
}

4.插入排序

对于第n个元素，我们先用tmp记录它的值，如果比前一个元素小,前一个元素就后移，直到大于等于前一个数，或者到0下标结束，最后在结束位置插入tmp。

插入排序的基本思路：
从第二个元素开始，将当前元素与前面已经排好序的部分进行比较。
找到合适的位置，将当前元素插入到该位置。
重复这个过程，直到整个序列有序。
插入排序的过程
1.以数组 [5, 2, 9, 1, 5, 6] 为例，插入排序的过程如下：

从第二个元素 2 开始，将其与前面的元素 5 比较。2 小于 5，所以交换它们。
2.数组变成 [2, 5, 9, 1, 5, 6]
处理第三个元素 9，9 大于 5，不需要交换。
3.数组仍然是 [2, 5, 9, 1, 5, 6]
处理第四个元素 1，将其与前面的元素逐一比较，直到找到合适的位置。1 小于所有的元素，所以将其放在最前面。
4.数组变成 [1, 2, 5, 9, 5, 6]
处理第五个元素 5，与前面的元素逐一比较，找到合适位置，将其插入到 [2, 5, 9] 和 6 之间。
5.数组变成 [1, 2, 5, 5, 9, 6]
处理第六个元素 6，将其插入到 9 和 5 之间。
6.数组变成 [1, 2, 5, 5, 6, 9]
最终，整个数组变成了 [1, 2, 5, 5, 6, 9]，即排序完成。

// 插入排序
void InsertSort(int* a, int n)
{int i;for(i=0;i<n-1;i++)//排n个元素 循环n-1次 {int end=i;//0~end有从小到大的顺序 int tmp=a[end+1];//记录a[end+1]的值 while(end>=0){if(tmp<a[end])//比后面小就覆盖(本质还是互换) {a[end+1]=a[end]; end--;}else break;//比后面大就终止 }a[end+1]=tmp;//在终止位置上存入tmp }
}

5.希尔排序

希尔排序是插入排序变化来的，希尔排序可以分为预排序 细排。

预排序的目的是把无序的数组变成接近有序。我们可以把一组数组分为多组，在同一组中每个元素在原数组的下标之间的距离(gap)都是一样的，然后对每一组进行插入排序，使原数组接近有序。

细排通过插入排序(gap==1)把接近有序的数组变成有序。

//希尔排序 
void ShellSort(int* a, int n)
{int gap=n,i;while(gap>0){ gap/=2;//最终gap变1 for(i=0;i<n-gap;i++)//每组轮流排一次 {   int end=i; //end在一组内最后一个有序元素的下标 int tmp=a[end+gap];//tmp一组内最后一个有序元素的下一个元素 while(end>=0){if(tmp<a[end]){a[end+gap]=a[end];//比后面小就覆盖(本质还是互换) end-=gap;//比较下一个元素 }else break;//比后面大就终止}a[end+gap]=tmp;//在终止位置上存入tmp } }
}

时间复杂度大概为n^1.3。

6.快排

快排本质是利用二叉树递归的思想。

首先找一个值设为key(一般为首尾元素)，假设我们以第一个元素为key，先从最后一个元素开始找比key小的值，找到就停下，然后再从第一个元素开始找比key大的元素，找到就和比key小的值交换，一直循环。（如果以最后一个元素为key，就先从第一个元素开始找）

直到两者相遇，相遇结点的值再和key交换。此时key左边的值都比它小，右边的值都比它大。

(如果相遇结点的值比key大还交换吗？结论：相遇结点的值永远小于等于key 原因在代码中)

我们可以把key结点看作根，它的左边看作左子树，右边看作右子树。左右子树分别递归循环，排好中间位置的元素，直到子树只有一个结点，或者为空。

//快速排序
void QuitSort(int *a,int begin,int end)//begin第一个元素 end最后一个元素下标 
{int ki=begin,bi=begin,ei=end;//ki记录key值的下标 便于后面交换 if(begin>=end) return;//子树为空或者只有一个结点，直接返回 while(begin<end){if(a[end]>a[ki]) end--;//key对面的下标先动(一般以起点/终点为key) 找比key小的值 if(a[begin]<a[ki]) begin++;//找比key大的值 Swape(&a[end],&a[begin]);} Swape(&a[begin],&a[ki]);//此时key左边的值都比key小，右边都比key大 QuitSort(a,bi,ki-1);//遍历左子树 对key左边的值进行排序 QuitSort(a,ki+1,ei);//遍历右子树 对key右边的值进行排序
}
//begin和end相遇结点的值一定不大于key(从小到大排)
//1.begin碰end 此时end是不动的 说明a[end]<key
//2.end碰begin 这又可以分为2种情况
//(1)end和begin相遇前至少进行过一次交换 交换完后end先动碰到begin 因为交换过a[begin]<key
//(2)end和begin相遇前没有进行过交换 end会一直--直到碰到begin  此时begin和end同时指向key 

6.1快排的优化

1.取key随机性高，容易取到极端值

对与这个问题，我们可以采用三目取中法来解决。在数组开头 结尾 中间 3个值中取一个中间值并作为key。

我们写一个在3个数中返回中间值下标的函数就可以了

​
//三目取中 
int GetMidi(int *a,int begin,int end)
{int midi=(begin+end)/2;if(a[midi]<a[begin]){if(a[end]<a[midi]) return midi;else if(a[begin]>a[end]) return end;//此时midi是最小值 返回较小的 else return begin;} else  //a[midi]>=a[begin]{if(a[end]>a[midi]) return midi;else if(a[end]>a[begin]) return end;//此时midi是最大值 返回较大的 else  return begin;}
}​

2.函数递归太多 栈内存空间消耗大

我们知道在满二叉树中最后一层结点个数大约占整个二叉树的%50，最后二层占%75。

而在快排中如果需要排序的个数太少，没有必要去建立栈来排，我们可以直接采用插入排序解决。

再加上三目取中法，我们就可以写出下面的函数。

//优化快排 
void ImproveQuitSort(int *a,int begin,int end)//begin第一个元素 end最后一个元素下标 
{   if(end-begin+1<10)//减少建栈(内存) 量少的直接用插入解决 {InsertSort(a,end-begin+1);return;}int ki=GetMidi(a,begin,end),bi=begin,ei=end;//三目取中ki取中间值的下标Swape(&a[begin],&a[ki]);//key与a[begin]交换 使key总位于起始位置 //if(begin>=end) return;//子树为空或者只有一个结点，直接返回 while(begin<end){if(a[end]>a[ki]) end--;//key对面的下标先动(一般以起点/终点为key) 找比key小的值 if(a[begin]<a[ki]) begin++;//找比key大的值 Swape(&a[end],&a[begin]);}Swape(&a[begin],&a[ki]);//此时key左边的值都比key小，右边都比key大 ImproveQuitSort(a,bi,ki-1);//遍历左子树 对key左边的值进行排序 ImproveQuitSort(a,ki+1,ei);//遍历右子树 对key右边的值进行排序
}

6.2快排（双指针法）

对于快排的实现，我们同样可以使用二个指针来解决。

1.取第一个元素为key，prve指向下标为0的元素，cur指向prve的前一个。

2.如果cur指向的值大于key cur就++，否则prve先++，再和cur交换，最后cur++。

3.当cur指向最后一个元素后面时，prve和key交换。

4.递归循环。

这个过程本质上就是不断的把大于key的值往后排，小于key的向前移。

（prve永远不会超过cur，因为无论cur大于还是小于key都会++）

//快排双指针法
void  PointerQuitSort(int *a,int begin,int end)
{if(begin>=end) return;int keyi=begin;//第一个元素为key int prev=begin;//prve指向begin int cur=prev+1;//cur在prve前面 while(cur<=end)//cur到最后一个元素后面结束 {if(a[cur]>a[keyi]) cur++;//如果cur指向的元素大于key就++ 小于key就停下 else Swape(&a[++prev],&a[cur++]);//否则prve先++ 再与cur指向元素交换 最后cur++ (先++是为了让prve指向大于key的值) }Swape(&a[prev],&a[keyi]);//当cur越界时 prev指向的值仍是小于key的 可以直接与key交换 keyi=prev;PointerQuitSort(a,begin,keyi-1);PointerQuitSort(a,keyi+1,end);
}

6.3快排（非递归）

我们可以利用栈结构来模拟递归过程。

我们可以把函数参数也就是begin，end压入栈，当一对begin，end处理完，再压入它右左子树的begin，end直到栈为空。因为栈是先进后出，如果想先处理左子树就先压入右子树，再压入左子树。

（注意入栈 出栈顺序，不要把左右范围搞反）

（压入左右子树范围时 注意不要越界）

//快排非递归
void StackQuitSort(int *a,int begin,int end)
{ST q;StackInit(&q);StackPush(&q,end);//先压右边 StackPush(&q,begin);//再压左边 while(!StackEmpty(&q)){int left=StackTop(&q);//此时栈顶元素为begin StackPop(&q);int right=StackTop(&q);StackPop(&q);if(left>=right) return;//用双指针进行一趟排序 int keyi=left;int prev=left;int cur=prev+1;while(cur<=right){if(a[cur]>a[keyi]) cur++;else Swape(&a[++prev],&a[cur++]); }Swape(&a[prev],&a[keyi]);keyi=prev;if(keyi+1<=right)//防止keyi+1越界 先压右右子树  {StackPush(&q,right);StackPush(&q,keyi+1);}if(keyi-1>=left)//再压左子树 (出栈时会先遍历左子树) {StackPush(&q,keyi-1);StackPush(&q,left);}}StackDestroy(&q);
}

7.归并排序

归并排序递归实现过程就像二叉树的后续遍历。

1.从中间不断分左右子树 直到剩1个结点时返回。

2.然后归并左右子树 较小的值存入tmp中，完成后把tmp复制到a中。

3.一级一级向上返回。

//归并排序
void _MergeSort(int *a,int begin,int end,int* tmp)
{if(begin==end) return;//只有一个不用排 int mid=(begin+end)/2;int i=begin;//记录起始位置 int begin1=begin,end1=mid;//左子树范围 int begin2=mid+1,end2=end; //右子树范围 _MergeSort(a,begin1,end1,tmp);_MergeSort(a,begin2,end2,tmp);while(begin1<=end1&&begin2<=end2)//左右子树中选取最小值存入 {if(a[begin1]>a[begin2]){tmp[i++]=a[begin1];begin1++;}else{tmp[i++]=a[begin2];begin2++;		}}while(begin1<=end1) tmp[i++]=a[begin1++];//将剩余元素按顺序存入数组 while(begin2<=end2) tmp[i++]=a[begin2++];memcpy(a+begin,tmp+begin,(end - begin + 1)*4);//将tmp排好数据复制到a 最后一个参数是字节数
} void MergeSort(int *a,int n)
{int *tmp=(int*)malloc(sizeof(int)*n);//给新建数组分配空间 if(tmp==NULL){perror("malloc fail");return ; }_MergeSort(a,0,n-1,tmp);//防止反复申请空间 再建一个函数进行递归free(tmp);tmp=NULL;return;
} 

7.1归并非递归

递归变非递归我们可以利用栈，队列或者直接用while循环来解决。

归并非递归直接从叶子结点（gap==1）开始，两个两个进行个归并。(gap为一组中的元素个数)

最后一层叶子结点归并完，进入下一层接着归并。

以此循环 直到一组中的元素大于整个数组的元素个数（gap>n）

//归并排序（非递归）
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//给新建数组分配空间 if (tmp == NULL){perror("malloc fail");return;}int gap = 1;//gap为一组中要排序的个数（可以理解为子树中结点个数）int i,j;while (gap < n)//一组中的个数要小于等于n 两组两组就行归并{for (i = 0; i < n; i += 2*gap)//i为初始位置 因为两两进行归并 所以i+=2*gap{j = i;//j记录初始位置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;//第二组元素有一部分 归并 要防止越界while (begin1 <= end1 && begin2 <= end2)//两组元素进行归并{if (a[begin1] > a[begin2]){tmp[j++] = a[begin1];begin1++;}else{tmp[j++] = a[begin2];begin2++;}}while (begin1 <= end1) tmp[j++] = a[begin1++];while (begin2 <= end2) tmp[j++] = a[begin2++];memcpy(a + i, tmp + i, (end2-i + 1) * sizeof(int));//i初始位置 end2终止位置}gap *= 2;//进入下一层 两组元素归并成一个所以*2}//本质上就是从叶子结点开始不断归并free(tmp);tmp = NULL;return;
}

实现代码时要注意1.左右子树范围不能越界

2.利用tmp对两组元素进行归并时，要用 j 先记录起始位置 i 后续j++不断存入下一个

8.计数排序

计数排序是对一组范围集中的数据进行排序，按顺序统计数组中相同元素出现的次数，同一个元素出现几次就输出几次。

1.首先我们要开辟一组数组tmp来记录数组中相同元素出现的次数，开辟数组的大小就要根据原数组值的范围来定，我们求出原数组中的max min就可以得出范围。

2.然后我们通过遍历的方式来出原数组中相同元素出现的次数。

3.最后根据tmp数组中记录的次数，有几次就在原数组中存入几次。

//计数排序
void CountSort(int *a,int n)
{int i,j=0,min=a[0],max=a[0];for(i=0;i<n;i++)//找出最大最小值 {if(min>a[i]) min=a[i];if(max<a[i]) max=a[i];}int range=max-min+1;//范围 int*tmp=(int*)malloc(sizeof(int)*range);if (tmp == NULL){perror("malloc fail");return;}memset(tmp,0,sizeof(int)*range);//初始化为0 for(i=0;i<n;i++)//记录不同数值出现几次 {tmp[a[i]-min]++;//因为不一定从0开始，所以要减去min }for(i=0;i<range;i++)//同一个值出现几次就输出几次 {while(tmp[i]){a[j++]=i+min; tmp[i]--;}}
}