题目描述： 给你一个整数数组 nums，将该数组升序排列。
上来的第一想法，居然就这么打卡成功了，哈哈哈哈哈哈哈哈
image
这个样子是肯定不行滴，要进步，就要自己亲力亲为，来，研究一下排序算法
image
插入排序： 简单插入排序 ----- 希尔排序 平均时间复杂由n2降低为n1.3，最坏时间复杂度，最好时间复杂度n2和空间复杂度o1均未变。
交换排序：冒泡排序 ------ 快速排序 平均时间复杂度由n2降低为nlogn，最坏时间复杂度由n2降低为nlogn，最好时间复杂度有损失，由n变为nlogn，空间复杂度有损失，由n变为nlogn
选择排序：简单选择排序 ----- 堆排序 平均时间复杂度又n2降低为nlogn，最坏时间复杂度由n2降低为nlogn，最好时间复杂度由n2降低为nlogn，空间复杂度是O1没有变化
// // Created by Xue,Lin on 2020/6/18. // #ifndef UNTITLED_SORT_ALGORITHM_H #define UNTITLED_SORT_ALGORITHM_H void swap(int &a, int &b) { // cout << "break3" << endl; int tmp = a; a = b; b = tmp; } // 希尔排序是插入排序，堆排序是选择排序，冒泡排序和快速排序是交换排序 // 1.插入排序 稳定，不占用额外空间，平均时间复杂度和最坏时间复杂度均为n2 // 思路为找到每个元素该在的位置，n轮循环后前n个元素有序，比较n+1元素和前n个元素 // 找到n+1元素应在位置，插入，此时前n+1元素有序 // 两轮循环 // 最坏时间复杂度n2，平均时间复杂度n2 // 最好情况为整个数组有序，每个元素仅需要和前一个元素比较，复杂度n // 因此比较是个基本有序的数组 // 注意数组作为参数传递，一定要传递数组长度，在函数内无法判断长度 void insertSort(int a[10], int n) { for(int i = 1; i < n; i++) { if (a[i] > a[i - 1]) { continue; } for(int j = i - 1; j >= 0; j--) { if (a[j+1] < a[j]) { swap(a[j+1], a[j]); } else { break; } } } } // 2.冒泡排序 // 注意是相邻元素比较，如果想把最大的先捞出来，第二重循环就从前往后遍历 // 如果是想把最小的先捞出来，第二重循环就从后往前遍历 void bubbleSort(int a[], int n) { for(int i = 0; i < n; i++) { for(int j = n; j >= i; j--) { if (a[j-1] > a[j]) { swap(a[j-1], a[j]); } } } } // 3.快速排序，冒泡排序的升级，属于交换排序类 // 快速排序基本思想为通过一趟排序将待排序的记录分割成两个独立的部分 // 其中一部分记录的关键字均比另外一部分要小，然后对这两部分进行分别排序 // 最终实现整个数组有序 // partition是快排的精髓部分，交换原始表a中数据位置，使小于枢纽值在左，大于枢纽值在右，最终返回枢纽所在位置 int partition(int a[], int low, int high) { // 枢纽值设定为带排序数组第一个元素 // 由于枢纽值的选取会影响快排效率，有改进法为3数选取，即在待排序数组中任选3个数，取中间数为枢纽 int pivot_value = a[low]; // 交换方式为low和high两个指针移动， // 先移动high，high--，当high小于pivot，交换，然后开始low++，当low大于pivot，交换 // 再移动high，重复上面过程，知道low和high相遇，代表此时partition结束 while(low < high) { // cout << "low:" << low << " " << "high:" << high << endl; // 注意high要是有效的 while(low < high && a[high] >= pivot_value) { high--; } swap(a[high], a[low]); // 注意这里要判断low < high 并且 a[low] 小于等于而不是小于，不然遇到相等的会一直出不去 while(low < high && a[low] <= pivot_value) { low++; } swap(a[low], a[high]); } return low; } void quickSort(int a[], int low, int high) { if (low >= high) { return; } int pivot; pivot = partition(a, low, high); quickSort(a, low, pivot - 1); quickSort(a, pivot + 1, high); } void quickSort(int a[], int n) { quickSort(a, 0, n - 1); } // 4.归并排序 // 归并排序的原理是假设原始序列包含n个记录，可以看成是n个有序的子序列，每个子序列的长度为1 // 然后两两归并，得到【n/2】个长度为2的子序列，再两两归并，直到整个序列有序 void merge(int a[], int begin, int mid, int end) { cout << "begin: " << begin << "end: " << end << endl; int *arr = new int(end-begin); // 将a中begin到end按照从小到大归并到arr，其中【begin，mid），【mid，end）是两个有序子序列 int l1 = begin, l2 = mid; int index = 0; while(l1 < mid && l2 < end) { if (a[l1] < a[l2]) { arr[index] = a[l1]; l1++; } else{ arr[index] = a[l2]; l2++; } index++; } while(l1 < mid) { arr[index++] = a[l1++]; } while(l2 < end) { arr[index++] = a[l2++]; } for(int i = begin; i < end; i++) { a[i] = arr[i-begin]; } return; } void msort(int a[], int begin, int end) { if (begin >= end - 1) { return; } int mid = begin + (end - begin) / 2; cout << "begin: " << begin << "end: " << end << "mid:" << mid << endl; msort(a, begin, mid); msort(a, mid, end); merge(a, begin, mid, end); return; } void mergeSort(int a[], int n) { msort(a, 0, n); } // 5.堆排序 // 堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子的节点值，称为大顶堆 // 每个节点值都小于或等于其左右孩子的节点值，称为小顶堆 // 堆排序就是利用堆进行排序的方法。将待排序数组构造成一个大顶堆，此时，这个序列的最大值就是堆顶 // 将他移走（就是把堆顶和堆数组末尾元素交换，此时末尾元素就是最大值） // 然后将剩余n-1个序列重新构造一个堆，这样就会得到n个元素中次大值 // 反复重复，可以得到一个有序序列 // 所以核心是实现两个函数 1.根据当前序列构建一个堆 2.在输出堆顶元素后，如何调整剩余元素成为一个新堆 // 参考链接：https://www.cnblogs.com/wanglei5205/p/8733524.html void headAdjust(int a[], int begin, int end) { // 核心函数，建立堆 // begin为第一个非叶子节点的下标 // cout << "begin:" << begin << "end:" << end << endl; int temp, j; temp = a[begin]; for(j = 2*begin; j < end - 1; j=j*2) { // 找到一个比较大的元素和当前元素进行交换 if (j < end - 1 && a[j] < a[j+1]) { j++; } if (temp >= a[j]) { break; } a[begin] = a[j]; begin = j; } a[begin] = temp; // cout << "begin:" << begin << "end:" << end << endl; return; } void headSort(int a[], int n) { int i; // 两个循环 // 第一个循环根据序列建立一个堆 for(i = n / 2; i >= 0; i--) { // cout << "break 1" << endl; // 从第一个非叶子节点开始，当前非叶子节点大顶堆，一步步往上推 headAdjust(a, i, n); } /* 可以把树结构打出来，验证问题，打出来就是按每层从左到右 for(int i = 0; i < n; i++) { cout << a[i] << " "; } */ // 第二个循环为移除顶点，然后重新建立堆 for(i = n; i >= 1; i--) { // cout << "break2" << endl; swap(a[0], a[i-1]); // 这个时候因为交换了顶点，因此顶点不满足大顶堆，但是其余根节点还是满足的 // 因此这里begin参数传0就可以 headAdjust(a, 0, i-1); /* for(int i = 0; i < n; i++) { cout << a[i] << " "; } */ } return; } // 6.希尔排序 // 希尔排序是插入排序的升级，看好的是插入排序相对基本有序数组排序较为高效的特点 // 希尔排序的思想是，每次循环完成对间隔为increment数组的排序，直到increment为1，即为完成全数组排序 void shellSort(int a[], int n) { int increment = n; do{ increment = increment / 3 + 1; cout << increment << endl; for(int i = increment; i < n; i++) { // cout << "i:" << i << endl; int tmp = a[i]; if (a[i - increment] > tmp) { // 寻找当前tmp插入的最合适的位置，应该插入到比他小的元素的前面，后面的元素都后移 int j = i - increment; for( ; j >= 0 && tmp < a[j]; j-=increment) { // cout << "j:" << j << endl; // 后移 a[j+increment] = a[j]; } // tmp插入合适位置 a[j+increment] = tmp; } // 完成一次按间隔increment抽出来的数组的插入排序 } } while(increment > 1); } #endif //UNTITLED_SORT_ALGORITHM_H int a[10] = {1,4, 2, 7, 2, 3, 8, 9, 4}; // insertSort(a, 10); // bubbleSort(a, 10); // quickSort(a, 10); // shellSort(a, 10); // headSort(a, 10); mergeSort(a, 10); for(int i = 0; i < 10; i++) { cout << a[i] << " "; }
