一、初步认识
排序：就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中时，根据排序过程的要求不能在内外存之间移动数据的排序
二、直接插入排序
基本思想: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。( 即当插入第i个元素时，前面的array[0]……array[i-1]已经排好序，此时用array[i]的排序码与array[0]……array[i-1]的排序码进行比较，
找到插入位置将array[i]插入,原来位置上的元素顺序后移 )
但在起始情况时，并不知道待排元素中究竟哪一部分是有序的，所以起初只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
#include<stdio.h> void InsertSort(int* arr, int n)//升序 { for (int i = 0; i < n-1; ++i)//一共插入n-1趟 { int end = i; int temp = arr[end + 1]; while(end >= 0) { if (temp < arr[end]) { arr[end + 1] = arr[end]; --end; } else { break;//找到位置 } } arr[end + 1] = temp; } } int main() { int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; InsertSort(arr, 10); for (int i = 0; i < 10; ++i){ printf("%d ", arr[i]); } return 0; }
时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 稳定
三、希尔排序
希尔排序（缩小增量排序），是直接插入排序的优化，其基本思想是：
1. 先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作。
2. 当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
为什么需要gap由大到小呢？
gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。
#include<stdio.h> void ShellSort(int* arr, int n)//升序 { int gap = n; while (gap > 1)//gap取值无官方规定(2、3……) { gap = gap / 3 + 1; //把间隔为gap的多组数据同时排 for (int i = 0; i < n - gap; ++i) { int end = i; int temp = arr[end + gap]; while (end >= 0) { if (arr[end] > temp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = temp; } } } int main() { int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; ShellSort(arr, 10); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
时间复杂度: O(NlogN)
平均时间复杂度: O(N ^ 1.3)
《数据结构-用面相对象方法与C++描述》--- 殷人昆
空间复杂度: O(1) 稳定性: 不稳定
四、直接选择排序
基本思想: 在元素集合中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，再在剩余的集合中重复上述步骤，直到集合剩余1个元素
#include<stdio.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void SelectSort(int* arr, int n) { for (int i = 0;i < n - 1;++i) { int min = i; for (int j = i+1; j < n; ++j) { if (arr[j] < arr[min]) { min = j; } } if (min != i) { Swap(&arr[i], &arr[min]); } } } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; SelectSort(arr, (int)(sizeof(arr) / sizeof(int))); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
优化: 每一趟遍历可以同时查找最大值和最小值，效率提升一倍
#include<stdio.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void SelectSort(int* arr,int n) { for (int begin = 0,end = n - 1; begin < end; ++begin, --end) { int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; ++i) { if (arr[i] < arr[mini]) mini = i; if (arr[i] > arr[maxi]) maxi = i; } Swap(&arr[begin], &arr[mini]); if (begin == maxi)maxi = mini;//前面的交换可能改变了此趟最大值的位置 Swap(&arr[end], &arr[maxi]); } } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; SelectSort(arr, (int)(sizeof(arr) / sizeof(int))); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 不稳定
五、堆排序
堆排序也属于选择排序中的一种。具体可以看下面这篇文章:
(28条消息) 堆结构的深度理解_GG_Bond19的博客-CSDN博客_堆的深度
https://blog.csdn.net/GG_Bruse/article/details/127742947
六、冒泡排序
这个算法的思想与它的名字息息相关，即通过交换每一趟冒出一个最大（或最小）值
#include<stdio.h> void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void BubbleSort(int arr[],int n) { for (int i = 0; i < n; ++i) { int exchange = 0; for (int j = 0; j < n-i-1; ++j) { if (arr[j] > arr[j+1]) { Swap(&arr[j], &arr[j + 1]); exchange = 1; } } if (exchange == 0) {//若没发生交换，则已有序 break; } } } int main() { int arr[10] = { 10,9,8,7,4,3,2,1,6,5 }; BubbleSort(arr, (int)(sizeof(arr) / sizeof(int))); for (int i = 0; i < 10; ++i) { printf("%d ", arr[i]); } return 0; }
时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 稳定
