插入排序
思路(这里以升序为例):
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)