leetcode 数组排序

leetcode: 排序数组排序算法包括基础的选择排序、插入排序、交换排序也包括堆排序、快速排序、归并排序(归并排序的典型应用场景是对链表进行排序)等。其中堆排序是选择排序的升级版快速排序是交换排序的升级版。那插入排序有没有升级版呢也是有的希尔排序但是希尔排序的思想不好理解所以本文中不涉及希尔排序。选择排序插入排序交换排序属于基础排序算法时间复杂度是O(n * n)。快速排序和堆排序的时间复杂度是O(nlogn)。O(logn)这种时间复杂度跟二分法的思想是很紧密的也就是说对数据集进行处理的时候每一次都是将上一次的数据集划分成两份然后分别对这两份做计算快速排序和堆排序否符合这样的规律。讨论排序算法的时候还常常要考虑算法的稳定性。比如有一个数据序列是 {5, 10, 100, 90, 80 100}其中第3个数和第6个数都是100排序之后的序列是{5, 10, 80, 90, 100, 100}如果排序之后的两个100没有改变原来的先后顺序也就是原来第三个位置的100排序后成为了第 5 个位置的 100原来第6个位置的100保持位置不变这样就是稳定的否则是不稳定的。排序算法时间复杂度是否稳定选择排序O(n * n)否插入排序O(n * n)是交换排序O(n * n)是快速排序O(nlogn)否堆排序O(nlogn)否归并排序O(nlogn)是在排序过程中边界条件是特别要注意的。对于排序算法的稳定性能保证稳定那么就是稳定的。因为在比较的时候可以带等号也恶意不带等号两种情况下的稳定性可能是不同的那么哪种方式能保证稳定就使用哪种方式。1 选择排序如下是选择排序的代码典型的两层循环时间复杂度是 O(n * n)。选择排序、插入排序、交换排序都是两层循环区别在于循环中的处理逻辑。 选择排序是选择一个最小的或者选择一个最大的数然后将这个最值放到一定的位置。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int i 0; i n - 1; i) { int min_index i; for (int j i 1; j n; j) { if (nums[j] nums[min_index]) { min_index j; } } int tmp nums[i]; nums[i] nums[min_index]; nums[min_index] tmp; } return nums; } };选择排序是不稳定的如下边的数据序列{100, 100, 50, 20, 10}在第一次选择的时候最小值是 10,10 和第 1 个位置的 100 进行交换。这样原来第一个位置的 100 和第二个位置的 100 就改变了先后顺序所以是不稳定的。2 交换排序交换排序又称为冒泡排序就像下雨的时候河面上冒起的水泡一样。从前向后两两对比如果前者较后者大那么就进行交换否则不交换。算法也是两层循环和选择排序相比除了循环中的逻辑不一样之外两个循环的起始索引也是不一样的。内层循环的起始索引或者结束索引受外层循环的 i 影响外层循环的起止索引往往也不是从 0 到 n - 1而是差一个。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int sorted_len 0; sorted_len n; sorted_len) { for (int i 0; i n - sorted_len - 1; i) { if (nums[i] nums[i 1]) { int tmp nums[i]; nums[i] nums[i 1]; nums[i 1] tmp; } } } return nums; } };冒泡排序是稳定的。如下数据序列相邻的两个数据进行比较的时候只有前者比后者大的时候才会交换否则不交换。所以对于两个相等的数值排序前后的先后顺序是保持不变的。{100, 100, 50, 20, 10}3 插入排序插入排序是稳定的。有一个已经存在的队列选择数据在这个队列中找到合适的位置将数据放到合适的位置。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int sorted_len 1; sorted_len n; sorted_len) { int data_index_to_insert sorted_len; int data nums[data_index_to_insert]; for (int i 0; i data_index_to_insert; i) { if (data nums[i]) { for (int k data_index_to_insert; k i; k--) { nums[k] nums[k - 1]; } nums[i] data; break; } } } return nums; } };插入排序也可以实现成下边的代码。插入排序就是选择一个数据向已经排序好的队列中插入数据那么具体把这个数据插入到队列的哪个位置呢查找位置的过程可以从前向后进行查找也可以从后向前查找。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int sorted_len 1; sorted_len n; sorted_len) { int data_index_to_insert sorted_len; int data nums[data_index_to_insert]; int i data_index_to_insert; for (; i 0 ; i--) { if (nums[i] nums[i - 1]) { nums[i] nums[i - 1]; nums[i - 1] data; } else { break; } } } return nums; } };插入排序是稳定的。如下的数据序列当将一个选择数值插入到已经排好序的队列时这个选择的数值本来在后边如果选择插入点的时候只要选择的值小于当前这个值就将选择的值插入到这个位置这样就可以保证稳定性。{100, 100, 50, 20, 10}选择排序、交换排序、插入排序都有两层循环时间复杂度均是 O(n * n)区别在于算法的侧重点是不一样的。其实选择排序中也有交换的思想选择一个最大值或者最小值之后将这个最值与排好序的位置进行交换交换排序也有选择的思想在一遍冒泡的过程中最终选择出来剩余数据的最大值或者最小值这就是选择插入排序中也有交换的思想给选择的数据找到一个合适的位置之后与此位置的数据进行交换。4 快速排序快速排序属于分治算法类似于二分查找二分查找也属于分治算法。快速排序是不稳定的。如下的数据序列首先选择第一个数 100然后进行比较。右半段的数值比 100 小的时候进行交换那么从右向左遍历到 1 的时候就要交换那么 1 会换到最左边。那么此时第 2 个位置的 1 就在第 8 个位置的 1 的后边了所以是不稳定的。{100, 1, 2, 10, 50, 100, 100, 1, 100, 200, 300, 500}class Solution { public: vectorint sortArray(vectorint nums) { QuickSort(nums, 0, nums.size() - 1); return nums; } // 快速排序是递归算法 void QuickSort(vectorint nums, int start, int end) { // 递归退出条件 // start end 的时候不需要进行排序了 if (start end) { return; } // 选择 start 位置的数作为比较和交换的对象 int select_data nums[start]; int select_index start; int start_tmp start; int end_tmp end; // 给选的数找到一个合适的位置需要通过 1 次或多次循环才能找到合适的位置 while(start_tmp end_tmp) { // 从小到大排序并且选择的是最左边的数值那么先从右边来遍历 // 如果数值比选择的数值大那么停止遍历循环遍历 // 如果数值不比选择的数值大那么 while (start_tmp end_tmp nums[end_tmp] select_data) { end_tmp--; } // end_tmp 处的数值 选择的数值所以把这个数放到左边 if (start_tmp end_tmp) { nums[start_tmp] nums[end_tmp]; start_tmp; } while (start_tmp end_tmp nums[start_tmp] select_data) { start_tmp; } if (start_tmp end_tmp) { nums[end_tmp] nums[start_tmp]; end_tmp--; } } // 遍历完毕start_tmp end_tmp 不成立了 // 项一个极端的情况就是以此循环就没有执行 // 那么还是把选择的数值放到 start_tmp 位置就可以了 nums[start_tmp] select_data; // 这次选择的数据的位置已经确定了 // 所以下次递归计算的时候这个位置不再参与计算了 // 所以左区间的右边界是 start_tmp - 1 // 右区间的左边界是 start_tmp 1 QuickSort(nums, start, start_tmp - 1); QuickSort(nums, start_tmp 1, end); return; } };5 堆排序堆排序是不稳定的。堆排序算法-CSDN博客6 归并排序归并排序参考如下博客的第 2 节链表排序。链表算法题总结-CSDN博客