排序算法总结

排序算法分类

• 基于���较的排序
  • 通过比较大小来决定元素间的相对次序。
  • 可以证明时间复杂度下界为 O ( n l o g n ) O(nlogn) O(nlogn)，不可能突破这个复杂度达到更快。
  • 非比较类排序
    • 不通过比较大小来决定元素间的相对次序。
    • 时间复杂度受元素的范围以及分布等多种因素影响，不单纯取决于元素数量 N。

      ---

      比较类排序

      • 选择排序
        • 简单选择排序
          • 每次从未排序数据中找最小值，放到已排序序列的末尾。
          • 时间复杂度 O ( n 2 ) O(n^2) O(n2)。

            for(int i = 0;i  

          • 堆排序
            • 利用二叉堆高效地选出最小值，建立一个包含所有 n n n 个元素的二叉堆，重复 n n n 次从堆中取出最小值，即可得到有序序列。
            • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。

              void heap_sort(int a[], int n) {priority_queue q;for(int i = 0;i  

            • 插入排序
              • 简单插入排序
                • 从前到后依次考虑每个未排序数据，在已排序序列中找到合适位置插入。
                • 时间复杂度 O ( n 2 ) O(n^2) O(n2)。

                  for(int i = 1;i = 0 && nums[pre_index] > current) {nums[pre_index + 1] = nums[pre_index];pre_index--;}nums[pre_index + 1] = current; }

                • 希尔排序
                  • 希尔排序是对插入排序的优化 – 增量分组插入排序。
                  • 时间复杂度取决于增量序列（步长序列）的选取，最好序列可以做到 N 4 3 N^\frac43 N34​ 或 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。
                  • 交换排序
                    • 冒泡排序
                      • 不断循环扫描，每次查看相邻的元素，如何逆序，则交换。
                      • 时间复杂度 O ( n 2 ) O(n^2) O(n2)。

                        for(int i = 0;i  nums[j + 1]) {int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}}

                      • 快速排序
                        • 快速排序也是一个基于分治的算法。
                        • 从数组中选取中轴元素 pivot。
                        • 将小元素放在 pivot 左边，大元素放在右边。
                        • 然后分别对左边和右边的子数组进行快排。
                        • 快速排序和归并排序具有相似性，但步骤顺序相反。
                          • 归并排序：先排序左右子数组，然后合并两个有序数组。
                          • 快速排序：先调配出左右子数组，然后对左右子数组分别进行排序。
                          • 随机选取 pivot，期望时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)，最坏 O ( n 2 ) O(n^2) O(n2)

                            void quickSort(vector& arr, int left, int right) {if (left >= right) return;int pivot = partition(arr, left, right);quickSort(arr, left, pivot);quickSort(arr, pivot + 1, right);}int partition(vector& arr, int left, int right) {int pivot = left + rand() % (right - left + 1);int pivotVal = arr[pivot];while(left while(arr[left]  

                          • 归并排序
                            • 归并排序是一个基于分治的算法。
                            • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 。
                            • 原问题：把数组排序。
                            • 子问题：把数组前一半、后一半分别排序，然后再合并左右两半（两个有序数组）就可以了。

                              void mergeSort(vector& arr, int l, int r) {if (l >= r) return;int mid = (l + r) >> 1;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);return merge(arr, l, mid, r);}void merge(vector& arr, int left, int mid, int right) {vector tmp = vector(right - left + 1); // 临时数组int i = left, j = mid + 1;for(int k = 0;k  right || (i  // 合并两个有序数组tmp[k] = arr[i++];} else {tmp[k] = arr[j++];}}for (int k = 0;k