插入排序
思路（这里以升序为例）：
1.先用一个变量接收最后一个元素，这里是tmp
2.用tmp保存的元素与前面的进行比较，如果比前面小则把前面的覆盖到end+1的位置
3.覆盖之后end继续向前走，end+1，自然也跟着向前走，此时可以看到tmp的作用，就是保存最后一个元素
4.当end<0时，一轮比较结束，此时将tmp的值传给end+1，即队首的位置，还有一种情况可使一轮比较结束
当end位置的元素<tmp时，一轮比较结束，进行下一轮比较
void InsertSort(int* a, int n) { int end = n - 1; int tmp = a[end + 1]; for (int i = 0; i < n-1; i++) { end = i; tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else break; } a[end + 1] = tmp; } } int main() { int arr[] = {9,8,7,6,5,4,3,2,1,0 }; int n = sizeof(arr) / sizeof(arr[0]); InsertSort(arr, n); return 0; }
直接排序时间复杂度：O(N^2)
希尔排序
1.预排序：接近有序，将间隔为gap的数据分成一组
设置一个gap将数组分为几组，这里gap是3，将数组分为了3组
9 5 8 5一组，1 7 6一组，2 4 3 一组
我们先将第一个红色部分的进行排序，我们可以看到红色部分是按照升序的
void ShellSort(int* a, int n) { int gap = 3; int end = n - 1; int tmp = a[end + gap]; for (int i = 0; i < n-gap; i+=gap) { end = i; tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end=end-gap; } else break; } a[end + gap] = tmp; } } int main() { int arr[] = {9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); InsertSort(arr, n); return 0; }
2.对3个组分别进行排序，使这三个部分有序
void ShellSort(int* a, int n) { int gap = 3; for (int j = 0; j < gap; ++j) { for (int i = j; i < n - gap; i += gap) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } int main() { int arr[] = {9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); ShellSort(arr, n); return 0; }
也可以这样
void ShellSort(int* a, int n) { int gap = 3; for (int i = 0; i < n - gap; i ++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } int main() { int arr[] = {9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); ShellSort(arr, n); return 0; }
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1;//或gap=gap/2; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } int main() { int arr[] = {9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); ShellSort(arr, n); return 0; }
当gap是1的时候是直接排序，其余情况是预排序
希尔排序时间复杂度：O(N^1.3)
选择排序
// 最坏时间复杂度：O(N^2) // 最好时间复杂度：O(N^2) void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { // 选出最小的放begin位置 // 选出最大的放end位置 int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; ++i) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } Swap(&a[begin], &a[mini]); // 修正一下maxi if (maxi == begin) //如果没有这条语句，当最大数是首元素时，前面语句会把最小的元素换到首元素，而此时maxi指向首元素，首元素却不是最大值，后面再交换就会出错 maxi = mini; Swap(&a[end], &a[maxi]); ++begin; --end; } }
1.一开始让maxi 和 mini 为数组首元素的下标
2. 接着遍历数组，进行比较替换
直接选择排序最慢的排序之一
选择排序的时间复杂度不像前面几种排序方法那样，前面几种排序方法的时间复杂度不是一眼就能看出来的，而是要通过推导计算才能得到的。一般会涉及到递归和完全二叉树，所以推导也不是那么容易。但是选择排序就不一样了，你可以很直观的看出选择排序的时间复杂度：就是两个循环消耗的时间；
比较时间：T = （n-1)）+ （n -2）+（n - 3）.... + 1; ===>> T = [n*(n-1) ] / 2；
交换时间：最好的情况全部元素已经有序，则 交换次数为0；最差的情况，全部元素逆序，就要交换 n-1 次；
所以最优的时间复杂度 和最差的时间复杂度 和平均时间复杂度 都为 ：O(n^2)
2.使用选择排序对长度为100的数组进行排序，则比较的次数为（ ）
A.5050
B.4950
C.4851
D.2475
答案：B
解析：
选择排序，每次都要在未排序的所有元素中找到最值，
如果有n个元素，则
第一次比较次数： n - 1
第二次比较次数： n - 2
....
第n - 1次比较次数： 1
所有如果n = 100
则比较次数的总和：99 + 98 + ...... + 1
共4950次。
交换排序
冒泡排序
void BubbleSort(int* a, int n) { for (int j = 0; j < n; ++j) { int exchange = 0; for (int i = 1; i < n - j; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) { break; } } }
比较集中排序，这里十万个数据，冒泡排序很慢
冒泡排序：最坏情况时间复杂度：O(N^2),最好情况O(N)
