文章目录
一、选择排序1.1 选择排序基础1.2 代码演示1.3 选择排序的复杂度、稳定性以及使用场景1.3.1 时间复杂度1.3.2 空间复杂度1.3.3 排序稳定性1.3.4 使用场景二、冒泡排序2.1 冒泡排序基础2.2 代码演示2.3 冒泡排序的复杂度、稳定性以及使用场景2.3.1 时间复杂度2.3.2 空间复杂度2.3.3 排序稳定性2.3.4 使用场景三、插入排序3.1 插入排序基础3.2 代码演示3.3 插入排序的复杂度、稳定性以及使用场景3.3.1 时间复杂度3.3.2 空间复杂度3.3.3 排序稳定性3.3.4 使用场景四、希尔排序4.1 希尔排序基础4.2 代码演示4.3 希尔排序的复杂度、稳定性以及使用场景4.3.1时间复杂度4.3.2 空间复杂度4.3.3 排序稳定性4.3.4 使用场景五、快速排序5.1 快速排序基础5.2 代码演示5.3 快速排序的复杂度、稳定性以及使用场景5.3.1 时间复杂度5.3.2 空间复杂度5.3.3 排序稳定性5.3.4 使用场景一、选择排序
1.1 选择排序基础
工作原理：扫描整个列表，找出最小的元素，然后将最小的元素与第一个元素交换位置。接着从第二个位置开始扫描，找出n-1个元素中最小的元素，将其与第二位置上的元素交换位置。如此类推，做n-1次后排序结束。
动画演示过程：
1.2 代码演示
void SelectionSort(int a[],int n){int i,j,temp;for(i = 0;i < n;i++){for(j = i+1;j < n;j++){if(a[j]<a[i]){//如果后面元素的值小于前面的，则进行交换temp = a[j];a[j] = a[i];a[i] = temp;}}}
1.3 选择排序的复杂度、稳定性以及使用场景
1.3.1 时间复杂度
由上面的代码可以看出，选择排序是在两层循环中进行的。因此，不管是最坏，最好的情况，时间复杂度都是O(n^2)。但是，如果一开始就是升序的，则交换的次数为0，如果是降序的，则交换次数为n-1。（默认结果为升序排序）。
1.3.2 空间复杂度
选择排序完全就是比较和交换数据，只需要一个辅助空间用来存储待比较的元素的下标，并没有消耗更多的额外空间，因此其空间复杂度是O(1)。
1.3.3 排序稳定性
选择排序是一种不稳定的算法，因为如果前后两个元素的值相同，则经过排序后，两者的前后顺序发生变化。
Eg：数组 4、6、4、3、8，在对其进行第一遍循环的时候，会将第一个位置的4与后面的3进行交换。此时，就已经将两个4的相对前后位置改变了。因此选择排序不是稳定性排序算法。
1.3.4 使用场景
待排序序列中，元素个数较少时
二、冒泡排序
2.1 冒泡排序基础
工作原理：比较相邻的元素，将大的元素交换到右边的位置，重复多次后，最大的元素就“沉淀”到列表的最后一个位置。第二遍将第二大元素沉淀下去，n-1次后结束。
动画演示过程：
2.2 代码演示
void BubbleSort(int a[],int n){int i,j,temp;for(i = 1;i <= n-1; i++) {//若有n个数，则交换的次数是n-1;for(j = 0;j <= n-i;j++){if(a[j] > a[j+1]){temp = a[j];//如果左边的数大于右边的，则交换a[j]和a[j+1]的位置 a[j] = a[j+1];a[j+1] = temp;}}}}
2.3 冒泡排序的复杂度、稳定性以及使用场景
2.3.1 时间复杂度
默认结果为升序
(1)如果一开始就是升序排列，一趟扫描即可完成排序。所需的关键字比较次数C和交换次数M均达到最小值：
C(min) = n-1;M(min) = 0
因此，冒泡排序在最好情况下的时间复杂度为O(n)。
(2)如果一开始是降序排列，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和交换次数均达到最大值：
C(max) = 1+2+…+(n-1)=n*(n-1)/2
M(max)= 3n(n-1)/2
因此，冒泡排序在最坏情况下的时间复杂度为O(n^2)。
2.3.2 空间复杂度
冒泡排序完全就是比较和交换数据，只需要一个辅助空间用来存储待比较的元素的下标，并没有消耗更多的额外空间，因此其空间复杂度是O(1)。
2.3.3 排序稳定性
在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。
2.3.4 使用场景
待排序序列中，元素个数较少时
三、插入排序
3.1 插入排序基础
工作原理：先假定第一个为有序数列，后面的为无序数列，然后从第二个元素开始，插入到前面的有序数列中，直到所有元素都插入进去为止。
动画演示过程：
3.2 代码演示
void InsertSort(int a[],int n){int i,j,temp;for(i = 1;i < n;i++){if(a[i] < a[i-1]){j = i-1;//先标记现在的位置temp = a[i];while(j >= 0&&temp < a[j]){a[j+1] = a[j];j--;}a[j+1] = temp;//将待排序元素插入数组中}}}
3.3 插入排序的复杂度、稳定性以及使用场景
3.3.1 时间复杂度
默认结果为升序排列
(1)如果一开始的时候就是升序排序的话，只需要当前的数与前面一个数作比较就行了，这时一共需要n-1次，时间复杂度为O(n)。
因此，插入排序在最好的情况下的时间复杂度为O(n)。
(2)如果一开始的时候是降序排序的话，总次数为1+2+3+…+n-1 = n*(n-1)/2。
因此，插入排序在最坏的情况下的时间复杂度为O(n^2)。
(3)平均情况是，右半区每一个数，都和一半的左半区的数比较。总次数为1/2 + 2/2 + 3/2 + … + ( n - 1 )/2 = O(n^2)。
因此，插入排序在的平均时间复杂度为O(n^2)。
3.3.2 空间复杂度
插入排序完全就是比较和交换数据，只需要一个辅助空间用来存储待比较的元素的下标，并没有消耗更多的额外空间，因此其空间复杂度是O(1)。
3.3.3 排序稳定性
在使用插入排序时，元素从无序部分移动到有序部分时，必须是不相等(大于或小于)时才会移动，相等时不处理，所以插入排序是稳定的。
3.3.4 使用场景
待排序序列的元素个数不多，且元素基本有序。
四、希尔排序
4.1 希尔排序基础
工作原理:希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它与插入排序的不同之处在于，它会优先比较距离较远的元素，间隔慢慢减成1，插入排序的间隔一直就是1。希尔排序又叫缩小增量排序。
动画演示过程：
4.2 代码演示
void ShellSort(int a[],int n){int i,j,temp;int gap = n/2;//先让比较的间距为n/2;while(gap > 0){for(i = gap;i < n;i++){if(a[i - gap] > a[i]){//与直接插入排序差不多的思路，只是间距逐渐减小temp = a[i];j = i -gap;while(j >= 0&&a[j]>temp){a[j+gap] = a[j];j -= gap;}a[j+gap] = temp;}}gap /= 2;}}
4.3 希尔排序的复杂度、稳定性以及使用场景
4.3.1时间复杂度
(1)最好情况：T(n) = O(n^1.3)
(2)最坏情况：T(n) = O(n^2)
(3)平均情况：T(n) =O(n^(1.3-2))[注:与所分的序列有关]
4.3.2 空间复杂度
希尔排序完全就是比较和交换数据，只需要一个辅助空间用来存储待比较的元素的下标，并没有消耗更多的额外空间，因此其空间复杂度是O(1)。
4.3.3 排序稳定性
希尔排序是直接插入排序的优化版，在排序过程中，会根据间隔将一个序列划分为不同的逻辑分组，在不同的逻辑分组中，有可能将相同元素的相对位置改变。如[2,2,4,1]，按间隔为2，降序排序，前两个元素的相对位置就会改变。
因此，希尔排序是不稳定的排序方式。
4.3.4 使用场景
待排序序列元素较少时。
五、快速排序
5.1 快速排序基础
工作原理:通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序(在这里用到递归思想)，以达到整个序列有序。
动画演示过程：
5.2 代码演示
void QuickSort(int* a,int n){int i,j;int pivot = a[0];//让第一个数为基准i =0;j = n-1;while (i < j){while(i <j&&a[j] > pivot){j--;}if (i < j){a[i] = a[j];i++;}while (i < j&&a[i] <= pivot){i++;}if (i <j){a[j] = a[i];j--;}}a[i] = pivot;//此时i == j; if (i > 1){quicksort(a,i) ;//左递归 }if (n-i-1>1){quicksort(a+i+1,n-i-1);//右递归 }}
5.3 快速排序的复杂度、稳定性以及使用场景
5.3.1 时间复杂度
快速排序涉及到递归调用，所以快速排序的时间复杂度需要从递归算法的复杂度说起。
递归算法的时间复杂度为：T(n) = aT[n/b]+f(n)。
（1）最好情况就是每一次取到的元素都刚好平分整个数组
此时,时间复杂度为：T(n) = 2T[n/2]+f(n)
下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
T[n] = 2T[n/2] + n ----------------第一次递归
令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----------------第二次递归
= 2^2 T[ n/ (2^2) ] + 2n
令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束)
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。 .
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
T[n] = 2^m T[1] + mn ；其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数
又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；
因此，快速排序最好的情况下时间复杂度为：O(nlogn)。
(2)最差情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
因此，快速排序最差的情况下时间复杂度为：O(n^2)。
(3)平均时间复杂度：从最好情况的分析中可知，快速排序的最好情况就是按平均来的
因此，快速排序的平均时间复杂度等于最好情况下的时间复杂度，也为：O(nlogn)。
5.3.2 空间复杂度
快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据，其空间复杂度为O(logn)。
5.3.3 排序稳定性
在快速排序中，每一趟排序都需要选择pivot(基准)。此时，基准两边可能出现和基准元素相同的值。如序列[1,5,2,4,5,4,6,5]，如果选择了a[4]作为基准因子，那么a[1]和a[7]势必会被分到基准因子的同一侧，序列的稳定性被破坏。所以，快速排序是一种不稳定的排序算法。
5.3.4 使用场景
待排序序列元素较多，并且元素较无序
如果觉得《十大排序算法笔记（C语言）（一）选择排序 冒泡排序 插入排序 希尔排序 快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
