【排序】用动态图快速理解各种排序！

排序的相关概念

排序的定义：

将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。

排序的分类：

按照排序记录存放位置区分：

内部排序：待排序记录存放在内存外部排序排序过程中需对外存进行访问的排序

按照排序规则区分：

插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序

排序的基本方法：

比较两个关键字大小，并记录其中一个位置将记录从一个位置移动到另一个位置

排序的稳定性：

​ 如果两个数相同，对他们进行的排序结果为他们的相对顺序不变，则称这种排序是稳定的。

简单排序

一、插入排序：

插入排序的时间复杂度为n*n，是一种稳定排序方法。

（一）插入排序基本思想

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

（二）插入排序基本操作

第i次插入的数是a[i]，这时数组b中的b[0]~b[i-1]已经有序了，将a[i]插入到数组b中的合适位置。插入a[i]的过程，分为3个步骤：

从b[0]开始，在b[0]~b[i-1]范围内找第一个大于a[i]的数，其位置记为pos；

从b[i-1]开始，将b[i-1]~b[pos]复制到后一个位置，相当于将这些数“后移”一个位置；

将a[i]放置在b[pos]位置上，替换b[pos]。

（三）代码实现

#include<stdio.h> void main() { int a[10],b[10]; //输入的10个数及排序后的10个数 int i,j,k; int pos; //每个数的插入位置 printf("input 10 numbers:\n"); for(i=0; i<10; i++) //输入 scanf("%d",&a[i]); printf("\n"); for(i=0; i<10; i++) //将a[i]插入合适的位置 { //在数组b中，b[0]~b[i-1]已经有序了，给a[i]找到合适的位置 for(j=0; j<=i-1; j++) { if(b[j]>a[i]) break; } pos = j; //a[i]的插入位置 for(k=i-1; k>=pos; k--) //将b[pos]~b[i-1]后移一个位置 b[k+1] = b[k]; b[pos] = a[i]; //将a[i]放置在b[pos]位置上 } printf("the sorted numbers:\n"); for(i=0; i<10; i++) //输出 printf("%d",b[i]); printf("\n"); }

二、选择排序

简单选择排序的时间复杂度为n*n，是一种稳定排序方法。

（一）选择排序基本思想

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

（二）选择排序基本操作

第0趟：通过n-1次比较，从n个数中找出最小的数，将它与第0个数交换。第0趟选择排序完毕，使得最小的数被安置在第0个元素位置上。

第1趟：通过n-2次比较，从剩余的n-1个数中找出次小的数，将它与第1个数交换。第1趟选择排序完毕，使得次小的数被安置在第1个元素的位置上。

如此重复上述过程，共经过n-1趟选择交换后，排序结束。

（三）代码实现

int i, j, k, t; //t是用来交换a[k]和a[i]的临时变量 for(i=0; i<n-1; i++) //共进行n-1趟选择及交换 { k = i; //每i趟中最小的数初始为a[i] for(j=i+1; j<n; j++) //将a[i+1]~a[n-1]之间的每个数与a[k]比较 { if(a[j]<a[k]) k = j; } t = a[i]; a[i] = a[k]; a[k] = t; }

思考：

要进行多少趟选择？

要进行n-1趟选择，因此外循环的循环变量i的取值是从0到n-1（不取等号）。

在第i趟里怎么选？

第i趟要从a[i],a[i+1],…,a[n-1]中选择最小的数，记为a[k]。因此内循环的循环变量j的取值是从i+1到n-1。

在第i趟里怎么交换？

每趟选择最终交换的是a[i]和a[k]。

三、冒泡排序

冒泡排序的时间复杂度为n*n，是一种稳定排序方法。

（一）冒泡排序基本思想

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

（二）冒泡排序基本操作

比较第0个数与第1个数，若为逆序，即a[0]>a[1]，则交换；然后比较第1个数与第2个数；以此类推，直至第n-2个数和第n-1个数比较完为止，即第0趟冒泡排序结束。第0趟排序的结果是最大的数被安置在最后一个元素位置上。

对前n-1个数进行第1趟冒泡排序，结果使次大的数被安置在第n-1个元素位置。

如此重复上述过程，共经过n-1趟冒泡排序后，排序结束。

（三）代码实现

bool bexchange = true; //状态变量 for(j=0; j<n-1 && bexchange; j++) //共进行n-1趟比较 { bexchange = false; for(i=0; i<n-1; i++) //在第j趟中要进行n-1-j次两两比较 { if(a[i]>a[i+1]) //比较的是前后两个相邻的数a[i]和a[i+1]，如逆序，则交换 { bexchange = true; t = a[i]; a[i] = a[i+1]; a[i+1] = t; } } }

快速排序

快速排序的时间复杂度为n* logn，是一种不稳定排序方法。

这里比较难理解，一定要慢慢看，仔细想，最好在纸上写写画画帮助理解

（一）快速排序基本思想

快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

先从数列中取出一个数作为基准数。

分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

再对左右区间重复第二步，直到各区间只有一个数。

（二）快速排序基本操作

设置两个变量I、J，排序开始的时候：I=0，J=N-1；

以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；

从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；

从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；

重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)

采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。

（三）代码实现

void Quick_Sort(int A[],int low,int high) //low和high是数组的下标 { if(low<high) { int temp,t=A[low]; int l=low,h=high; while(l<h) { while(A[l]<t) l++; while(A[h]>=t) h--; if(h>l) { temp=A[l]; A[l]=A[h]; A[h]=temp; } } Quick_Sort(A,low,l-1); Quick_Sort(A,l+1,high); } }

qsort 排序

qsort函数是c/c++语言的库函数（包含在头文件stdlib.h中），采用快速排序算法实现，效率很高，经常使用。

（一）qsort函数的用法

qsort函数的原型为：

void qsort(void *base, int num, int width, int(*compare)(const void *elem1, const void *elem2));

它有四个参数，其含义为：

base：参与排序的元素存储空间的首地址，它是空类型指针；

num：参与排序的元素个数；

width：参与排序的每个元素所占字节数（宽度）；

第四个参数为一个函数指针，这个函数需要用户自己定义，用来实现排序时对元素之间的大小关系进行比较。compare函数的两个参数都是空类型指针，在实现时必须强制转换成参与排序的元素类型的指针。

（二）qsort函数的使用方法

1、 对基本数据类型的数组排序

如果数组元素是int型，且按从小到大的顺序（升序）排序，compare函数可以编写成：

int compare(const void *elem1, const void *elem2){ return *(int *)elem1 - *(int *)elem2; }

Compare函数定义好以后，就可以用下面的代码段实现一个整型数组的排序：

int num[100]; … //输入100个数组元素的值 qsort(num, 100, sizeof(num[0]), compare); //调用qsort函数进行排序

对char、double等其他基本数据类型数组的排序，只需把上述compare函数代码中的int型指针（int *）改成其他类型指针即可。

2、 对结构体一级排序

所谓对结构体一级排序，是指对结构体中的某一个成员的大小关系排序。

struct student{ char name[20]; //姓名 int age； //年龄 double score； //分数 }；

例如对上述的student数组s中的元素以其age成员的大小关系从小到大排序。

compare函数可以定义成：

int compare(const void *elem1, const void *elem2){ return((student *)elem1)->age – (student *)elem2->age; }

qsort函数调用形式为：

qsort(s, 10, sizeof(s[0]), compare);

3、 对结构体二级排序

对结构体二级排序，含义是先按某个成员的大小关系排序，如果该成员大小相等，再按另一个成员的大小关系进行排序。比如上面的student数组s，可以先按age成员从小到大的顺序排序，如果age成员大小相等，再按score成员从小到大的顺序排序。

compare函数定义如下：

int compare(const void *elem1, const void *elem2){ student *p1 = (student *)elem1; student *p2 = (student *)elem2; if(p1->age != p2->age) return p1->age – p2->age; else return p1->score – p2->score; }

qsort函数调用形式为：

qsort(s, 10, sizeof(s[0]),compare);

其他排序

一、希尔排序

算法描述：

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。

二、归并排序

算法描述：

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。

三、桶排序

算法描述：

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

什么时候最快 当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢 当输入的数据被分配到了同一个桶中。

元素分布在桶中：

然后，元素在每个桶中排序：

四、计数排序

算法描述：

计数排序统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引 i 位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。计数排序不是比较排序，排序的速度快于任何比较排序算法。

---

堆排序和基数排序后续更新