十大基础排序算法

排序算法分类

排序：将一组对象按照某种逻辑顺序重新排列的过程。

• 按照待排序数据的规模分为：

  1. 内部排序：数据量不大，全部存在内存中；
  2. 外部排序：数据量很大，无法一次性全部存在内存中，因此排序中需要访问外存。

• 按照排序是否稳定分为：

  1. 稳定排序：相等的元素在排序前后的相对位置不变。例如，a等于b，且原序列a在b前，排序后a仍在b前，则为稳定排序。
  2. 不稳定排序：相等元素在排序前后的相对位置可能发生变化。

• 按照是否需要额外内存分为：

  1. 原地排序：在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
  2. 非原地排序：需要额外内存空间存储数组副本以辅助排序。

• 按照排序方式分为：

  1. 比较类排序：通过比较来决定元素间的相对次序。
  2. 非比较类排序：不通过元素间的比较进行排序。

  比较类排序

  冒泡排序

  冒泡排序是一种典型的交换排序。

  算法原理：

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这一步结束后，排在最后的元素会是所有数据中最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    冒泡排序基本代码如下：

    void BubbleSort(vector& nums){ const int size = nums.size();
        for(int i = 0; i < size; ++i)
            for(int j = 0; j < size-i-1; ++j)
                if(nums[j] > nums[j+1])
                    swap(nums[j], nums[j+1]);
    }
    

    性能评价：

    • 当nums[j] == nums[j+1]时，我们并不交换它们。所以冒泡排序是稳定的;
    • 共循环了(n-1)+(n-2)+…+2+1=n(n-1)/2,所以时间复杂度是O(n^2)。

      快速排序

      快速排序是从冒泡排序演变而来的，实际上是在冒泡排序基础上的递归分治法。

      快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

      快排也用了分治策略，其本质框架类似二叉树的前序遍历。

      其实现代码如下：

      void QuickSort(std::vector& nums, int left, int right){ if(left >= right){ return;
          }
          //"治"
          int i = left;
          int j = right;
          while(i < j){ while(i < j && nums[j] > nums[left])     --j;
              while(i < j && nums[i] <= nums[left])    ++i;
              std::swap(nums[i], nums[j]);
          }
          std::swap(nums[i], nums[left]);
          //“分”
          QuickSort(nums, left, i - 1);
          QuickSort(nums, i + 1, right);
      }
      

      注意事项

      1. 如果选取数列的第一个元素为基准元素，则从right所指向的元素开始与基准元素进行比较；如果选取数列的最后一个元素为基准元素，则从left所指向的元素开始与基准元素进行比较。
      2. 如果选取数列的第一个元素为基准元素，left所指向的元素与基准元素第一次对比时，left下标与基准元素下标相等（即：判断条件中添加等号）；如果选取数列的最后一个元素为基准元素，right所指向的元素与基准元素第一次对比时，right下标与基准元素下标相等。

      时间复杂度：O(nlogn)

      空间复杂度：O(1)

      稳定性：不稳定

      插入排序

      基本思想：将待排序数据看成由已排序和未排序两部分组成。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

      算法流程：

      1. 从第一个元素开始，该元素可以认为已经被排序；
      2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
      3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
      4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
      5. 将新元素插入到该位置后；
      6. 重复步骤2~5。

      其实现代码如下：

      void InsertSort(vector& nums){ const int size = nums.size();
          for(int i = 1; i < size; ++i){ int curr = nums[i];
              int j = i - 1;
              while(j >= 0 && curr < nums[j]){ nums[j+1] = nums[j];
                  --j;
              }
              nums[j+1] = curr;
          }
      }
      

      性能评价：

      • 插入排序是稳定的。
      • 时间复杂度为O(n^2)。

        希尔排序

        在插入排序中，当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

        希尔排序是对插入排序的优化。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

        其实现代码如下：

        void ShellSort(std::vector& nums){ const int size = nums.size();
            for(int gap = size / 2; gap > 0; gap /= 2){ for(int i = gap; i < size; ++i){ int curr = nums[i];
                    int j = i - gap;
                    while(j >= 0 && curr < nums[j]){ nums[j+gap] = nums[j];
                        j -= gap;
                    }
                    nums[j+gap] = curr;
                }
            }
        }
        

        选择排序

        基本思想：首先在未排序数据找到最小的数，然后把该最小数放到排序序列的末尾，直到所有数据排序完毕。

        其实现代码如下：

        void SelectionSort(vector& nums){ const int size = nums.size();
            for(int i = 0; i < size-1; ++i){ int minIndex = i;
                for(int j = i+1; j < size; ++j)
                    if(nums[j] < nums[minIndex])
                        minIndex = j;
                swap(nums[i], nums[minIndex]);
            }
        }
        

        性能评价：

        • 简单选择排序是不稳定排序；
        • 无论什么数据进去，它的比较次数都是n(n-1)/2,所以时间复杂度是O(n^2)。

          堆排序

          首先将等待排序的数组构造成一个大根堆，构造结束后整个数组当中的最大值就是堆顶元素；

          然后将堆顶元素与数组末尾元素交换位置，交换结束后数组末尾元素为最大值，剩下其他的待排序的数组个数为n-1个；

          将剩余的n-1个数再次构造成一个大根堆，再将堆顶元素与数组第n-1个位置的元素交换位置，重复上述步骤可以最终得到一个有序数组。

          其实现代码如下：

          //堆调整
          void Heapify(std::vector& nums, int index, int heap_size){ int parent_index = index;
              int leftChild_index = 2 * parent_index + 1;
              while(leftChild_index < heap_size){ int maxValue_index = leftChild_index+1 < heap_size && nums[leftChild_index+1] > nums[leftChild_index] ? leftChild_index+1 : leftChild_index;
                  maxValue_index = nums[maxValue_index] > nums[parent_index] ? maxValue_index : parent_index;
                  if(maxValue_index == parent_index)
                      return;
                  std::swap(nums[maxValue_index], nums[parent_index]);
                  parent_index = maxValue_index;
                  leftChild_index = 2 * parent_index + 1;
              } 
          }
          //堆排序
          void HeapSort(std::vector& nums){ if(nums.size() < 2)
                  return;
              int heap_size = nums.size();
              //从下标最大的父节点开始。（最后一个元素的下标是n-1，最后一个父节点的下标是n/2-1）
              for(int i = heap_size/2 - 1; i >= 0; --i)
                  Heapify(nums, i, heap_size);
              std::swap(nums[0], nums[--heap_size]);
              while(heap_size > 0){ Heapify(nums, 0, heap_size);
                  std::swap(nums[0], nums[--heap_size]);
              }
          }
          

          时间复杂度：O(nlogn)

          空间复杂度：O(1)

          稳定性：不稳定

          归并排序

          简单归并排序即二路归并排序。

          归并排序采用分治策略，其本质框架类似二叉树的后序遍历，左右子树的递归就是“分”，根结点的处理部分就是“治”。

          其实现代码如下：

          std::vector temp;
          void MergeSort(std::vector& nums, int left, int right){ if(left >= right){ return;
              }
              int mid = left + (right - left) / 2;
              //“分”
              MergeSort(nums, left, mid);
              MergeSort(nums, mid + 1, right);
              //"治"
              int i = left;
              int j = mid + 1;
              int t = left;
              while(i <= mid && j <= right){ if(nums[i] <= nums[j]){ temp[t++] = nums[i++];
                  }
                  else{ temp[t++] = nums[j++];
                  }
              }
              while(i <= mid){ temp[t++] = nums[i++];
              }
              while(j <= right){ temp[t++] = nums[j++];
              }
              for(int k = left; k <= right; ++k){ nums[k] = temp[k];
              }
          }
          

          时间复杂度：O(nlogn)

          空间复杂度：O(n)

          稳定性：稳定

          非比较类排序

          基数排序

          计数排序

          桶排序

          总结

          不稳定排序记忆口诀：一堆（堆排序）作业，心态不稳，快（快速排序）选择（选择排序）一些（希尔排序）朋友出去玩。