十大经典排序算法

前言

最近一直在找工作，面试中有遇到问排序算法的，所以花了点时间把十大经典排序算法用Objective-C实现了一遍，以便加深记忆。事实上，算法更重要的是思想，没必要死记硬背，只要理解了原理，就能很容易写出来。

术语解释

同一问题可用不同算法解决，那么比较之下就会出现算法优劣的问题。一个算法的评价主要从时间复杂度和空间复杂度来考量。此外，对于排序算法来说还要考虑它的稳定性和排序方式。下面是对这些术语的简单解释。

• 时间复杂度

  简而言之，就是一个算法执行所消耗的时间。算法的时间复杂度越大，算法的执行效率越低。按数量级递增排列，常见的时间复杂度有：

  $O(1)$：常量级，算法复杂度是一个常数。

  $O(n)$：线性级，算法复杂度是数据量$n$的线性函数。

  $O(n^2)$：平方级，与数据量$n$的二次多项式函数属于同一数量级。

  $O(n^3)$：立方级，是$n$的三次多项式函数。

  $O(logn)$：对数级，是$n$的对数函数。

  $O(nlogn)$：介于线性级和平方级之间的一种数量级。

  $O(2^n)$：指数级，与数据量$n$的指数函数是一个数量级。

  $O(n!)$：阶乘级，与数据量$n$的阶乘是一个数量级。

• 空间复杂度

  评估执行程序所需的存储空间，可以估算出程序对计算机内存的使用程度。不包括算法程序代码和所处理的数据本身所占空间部分。通常用所使用额外空间的字节数表示。其公式比较简单，记为$S(n)=O(f(n))$，其中，$n$表示问题规模。

• 稳定性

  对于排序算法而言，如果排序过程中遇到两个相等的数值a和b，排序前a在b的前面，排序后a仍然在b的前面，则为稳定排序；反之，则为不稳定排序。

• 排序方式

  如果一个排序算法在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序，则称为原地排序（In-place）;反之，称之为非原地排序（Out-place）。

算法实现

一、冒泡排序

• 算法思想

  将数组中第一个元素与第二个元素进行比较，如果第一个比第二个大，则交换他们的位置；接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置……以此类推，直到结尾的最后一对。这样一趟比较交换下来之后，排在最右的元素就会是最大的数。除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

• 代码实现

  + (void)bubbleSort:(NSMutableArray<NSNumber *> *)nums {
      NSInteger n = nums.count - 1;
      for (NSInteger i = 0; i < n; i++) {
          for (NSInteger j = 0; j < n-i; j++) {
              if ([nums[j] compare:nums[j+1]] == NSOrderedDescending) {
                  [nums exchangeObjectAtIndex:j withObjectAtIndex:j+1];
              }
          }
      }
  }

• 相关性质

  时间复杂度	空间复杂度	稳定性	排序方式
  $O(n^2)$	$O(1)$	稳定排序	原地排序

• 算法优化

  假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于或等于左边的元素，此时已经是有序的了，我们无需再对剩余的元素重复比较下去了。由此，我们可以在外层循环中设置一个flag，初始化为YES，当发生交换则置为NO。那么一轮比较下来，如果flag得值为YES，则直接break，结束排序。具体代码如下：

  + (void)bubbleSort:(NSMutableArray<NSNumber *> *)nums {
      NSInteger n = nums.count - 1;
      for (NSInteger i = 0; i < n; i++) {
          BOOL flag = YES;
          for (NSInteger j = 0; j < n-i; j++) {
              if ([nums[j] compare:nums[j+1]] == NSOrderedDescending) {
                  [nums exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                  flag = NO;
              }
          }
          if (flag) break;
      }
  }

二、选择排序

• 算法思想

  首先，找到数组中最小的那个元素，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）；然后，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

• 代码实现

  + (void)selectSort:(NSMutableArray<NSNumber *> *)nums {
      NSInteger n = nums.count;
      for (NSInteger i = 0; i < n-1; i++) {
          for (NSInteger j = i+1; j < n; j++) {
              if ([nums[i] compare:nums[j]] == NSOrderedDescending) {
                  [nums exchangeObjectAtIndex:i withObjectAtIndex:j];
              }
          }
      }
  }

• 相关性质

  时间复杂度	空间复杂度	稳定性	排序方式
  $O(n^2)$	$O(1)$	非稳定排序	原地排序

三、插入排序

• 算法思想

  1.抽取数组第二个元素，将它与左边第一个元素比较，如果比左边第一个元素小，则插到第一个元素的左边（也就是index=0的位置）；

  2.抽取数组第三个元素，将它与左边的元素按照自右向左的方向依次比较，遇到比它小的元素时终止比较，并插在这个元素的右边；

  3.继续选取第四、五……直到最后一个元素,重复步骤 2 。

• 代码实现

  + (void)insertSort:(NSMutableArray<NSNumber *> *)nums {
      NSInteger n = nums.count;
      for (NSInteger i = 1; i < n; i++) {
          for (NSInteger j = i; j > 0; j--) {
              if ([nums[j] compare:nums[j-1]] == NSOrderedAscending) {
                  [nums exchangeObjectAtIndex:j withObjectAtIndex:j-1];
              } else {
                  break;
              }
          }
      }
  }

• 相关性质

  时间复杂度	空间复杂度	稳定性	排序方式
  $O(n^2)$	$O(1)$	稳定排序	原地排序

四、快速排序

• 算法思想

  快速排序与其他排序算法相比，它的特点是：比较和交换次数少，在许多情况下可以高效的进行排序。具体思路是这样的：从数组中随机选择一个元素作为基准，这个元素被称为pivot；然后把数组中所有小于pivot的元素放在其左边，所有大于或等于pivot的元素放在其右边。显然，此时pivot所处的位置的是有序的，也就是说，我们无需再移动pivot的位置。从pivot那里开始把大的数组切割成两个小的数组（两个数组都不包含pivot）；接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1。此时，每个元素都处于有序的位置了。

• 代码实现

  + (void)quickSort:(NSMutableArray<NSNumber *> *)nums leftIndex:(NSInteger)left rightIndex:(NSInteger)right {
      if (left >= right) { // 如果数组长度为 0 或 1 时返回
          return;
      }
      
      NSInteger i = left;
      NSInteger j = right;
      NSNumber *pivot = nums[i]; // 记录比较基准数
      
      while (i < j) {
          // 首先从右边 j 开始查找比基准数小的值
          while (i < j && ([nums[j] compare:pivot] != NSOrderedAscending)) {
              j--; // 如果大于或等于基准数，继续查找
          }
          nums[i] = nums[j]; // 如果比基准数小，则将查找到的小值调换到 i 的位置
          // 当在右边查找到一个比基准数小的值时，就从 i 开始往后找比基准数大的值
          while (i < j && ([nums[i] compare:pivot] != NSOrderedDescending)) {
              i++; // 如果小于或等于基准数，继续查找
          }
          nums[j] = nums[i]; // 如果比基准数大，则将查找到的大值调换到 j 的位置
      }
      nums[i] = pivot; // 将基准数放到正确位置
      
      // 排序基准数左边的
      [Sort quickSort:nums leftIndex:left rightIndex:i-1];
      // 排序基准数右边的
      [Sort quickSort:nums leftIndex:i+1 rightIndex:right];
  }

• 相关性质

  时间复杂度	空间复杂度	稳定性	排序方式
  $O(nlogn)$	$O(logn)$	非稳定排序	原地排序

<先写到这吧，有时间再完善剩下的六种排序算法……>

打赏