八股文之排序算法

更新中

参考文献

	链接
	阿里五面：说下希尔排序的过程？ 希尔排序的时间复杂度和空间复杂度又是多少？
	快速排序和归并排序的时间复杂度分析——通俗易懂
	hello 算法

比较排序

简单排序

冒泡排序

经典的排序，实现和理解都很容易
思路：从数列最左端开始，依次比较相邻两数，按照需求，进行位置交换，比如要求从小到大，当左数比右数大时，两数交换，最终在最右端能得到当前乱序数列中最大的数。之后重复之前的操作，乱序数列不断减少
实现：双循环，每完成一次小循环，减少小循环次数。注意比较的次数为数列长度减一。

• 数据

  平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	算法稳定性
  $O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定

• 代码

public void BubbleSort(int[] array)
  {
      //外循环乱序数列[0,i]
      for (int i = array.Length - 1; i>0 ; i--)
      {
          //内循环[0,i]将最大值移动到最后一位
          for (int j = 0; j < i; j++)
          {
              //如果比下一位大，则交换
              if (array[j] > array[j + 1])
                  (array[j], array[j + 1]) = (array[j + 1], array[j]);
          }
      }
  }

选择排序

还是很经典
思路：从乱序中，按照要求，选择最大或者最小值，在遍历完当前乱序数列后，将记录的最值放入有序数列中，乱序数列不断缩短，最后变为有序数列
实现：双循环，用局部变量分别记录最值的指针位置和数值，在循环结束后，比较最值指针和当前头部指针，如果相同，说明不需要交换直接进行下一次选择，否则交换两数，然后头部指针后移。因为开始要有个默认的最值，所以大循环的次数为 n-1(n 为数列长度)

• 数据

  平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	算法稳定性
  $O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定

• 代码

public void SelectionSort(int[] array)
   {
       for (int i = 0; i < array.Length - 1; i++)
       {
           int tempMin = array[i]; //设当前指针所在位置为最小值，这个值可以没有，不过后面如果没有别的算法，就需要一个局部变量储存一个值
           int tempIndex = i; //设当前指针为最小值所在指针

           //从当前后一位开始，比较到最后一位
           for (int j = i + 1; j < array.Length; j++)
           {
               //如果当前数比记录的最小数都小，那就更新最小数和最小数指针
               if (tempMin > array[j])
               {
                   tempMin = array[j];
                   tempIndex = j;
               }
           }

           //如果没变 就不用交换
           if (tempIndex == i)
               continue;

           //如果变了，交换当前和记录的最小数
           (array[i], array[tempIndex]) = (array[tempIndex], array[i]);
       }
   }

插入排序

希尔排序会用到，见进阶排序/希尔排序
思路：扑克牌，从乱序数列中，抽一张，根据需求，插入到有序数列中
实现：默认乱序中第一个数为有序数列，从第二个数开始，向其中插数，与有序数列中的数依次比较，如果比当前有序数列被比较的数小，那么有序数列中的数向后移，直到找到合适的位置，将待插入的数插入。

如果在 for 循环语句中写条件，注意条件顺序，不然会出现指针超出范围的 bug

• 数据

  平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	算法稳定性
  $O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定

• 代码

public void InsertSort(int[] array)
   {
       int currentValue; //当前要插入的数
       int i;
       int j;
       //默认第一个数已经处于有序数组当中
       for (i = 1; i < array.Length; i++)
       {
           currentValue = array[i];
           //每次循环都新加一个数到有序数组，如果插入数比有序序列中当前值小，则有序序列数值前移 注意这里写入条件的顺序
           for (j = i; j > 0 && currentValue < array[j - 1]; j--)
               array[j] = array[j - 1];

           //结束之后，当前位置为要插入数的合适位置
           array[j] = currentValue;
       }
   }

进阶排序

希尔排序

又叫缩小增量排序
1959 年 Shell 发明，第一个突破 $O(n^2)$ 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素，通过不断分组，提高插入排序的效率。希尔排序的时间复杂度与增量序列的选取有关，所以希尔排序在中等大小规模表现良好，对规模非常大的数据排序不是最优选择。笔者个人对于希尔还有个理解，就是它和归并排序操作类似，因为下一次分组总会把上一次包裹进来，并且进行整合，就类似归并排序先分组，后将组归并。
思路：按照间隔分组，间隔一般默认初始为数组长度/2，然后分别对每组进行插入排序
实现：三层循环，每次循环结束，重新计算间隔。注意这里插入排序是对每组依次分段进行插入排序，不是一次性对单独某个组的一整段进行插入排序。

这个数据网上中说纷纭，笔者也不能判断真伪，建议读者自行查阅
图解排序算法(二)之希尔排序
菜鸟教程

• 数据

  平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	算法稳定性
  $O(n log^2 n)/O(n^{1.25})$	$O(n log n)$	$O(n^{1.5} )$	$O(1)$	不稳定

  希尔排序，如果用希尔增量序列$(n/2,(n/2)/2....1)$，能使其时间复杂度达到$O(n^2)$。一些经过优化的增量序列如 Hibbard 经过复杂证明可使得最坏时间复杂度为$O(n^{1.5})$

• 代码

public void ShellSort(int[] array, int interval)
  {
      int currentInterval; //当前间隔
      int index; //总指针
      int subIndex; //每组指针
      int insertSortValue; //插入算法当前值

      //缩小增量
      for (currentInterval = interval / 2; currentInterval > 0; currentInterval /= 2)
      {
          //每组进行多次插入排序
          for (index = currentInterval; index < interval; index++)
          {
              //要插入的值
              insertSortValue = array[index];
              //如果指针在有序区外，且要插入的值比前一个数要小，数组的值前移
              for (subIndex = index;
                   subIndex >= currentInterval && insertSortValue < array[subIndex - currentInterval];
                   subIndex -= currentInterval)
                  array[subIndex] = array[subIndex - currentInterval];

              //结束之后，说明该位置的值小于插入值
              array[subIndex] = insertSortValue;
          }
      }
  }

快速排序

采取分治思想（归并排序也用到了分治），运用比较广泛
思路：通过轴数，将数组分区，然后对分区再次取轴数，再分区，如此往复，直到分区长度为 1，即为有序数列
实现：先选取轴数，一般默认为数列首位，然后分区，比轴数小的放在轴数左边，大的放在轴数右边，这一步采取双指针，当左右指针重合时，该位置即为轴数应该放置的位置。之后用过递归，再次对两个分区进行取轴分区
注意，分区后，轴数不能再包含在分区中

• 数据

  平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	算法稳定性
  $O(n log n)$	$O(n log n)$	$O(n^2)$	$O(n)$	不稳定

• 代码

public void QuickSort(int[] array, int left, int right)
  {
      //如果已经重合，就不需要再排序了
      if (left >= right) return;

      int pivot = GetPivot(array, left, right); //先排序确认中轴数的位置
      QuickSort(array, left, pivot - 1); //左半边继续排序
      QuickSort(array, pivot + 1, right); //右半边继续排序
  }

  //排列并获取轴数指针位置
  private int GetPivot(int[] array, int left, int right)
  {
      //默认左指针为中轴数，同时也相当于左指针取数
      int pivotNum = array[left];
      while (left < right)
      {
          //右指针移动
          while (array[right] >= pivotNum && left < right)
          {
              right--;
          }

          //右指针停止移动，此时左指针指向的的数应该已经无效
          if (left < right) array[left] = array[right];

          //左指针移动
          while (array[left] < pivotNum && left < right)
          {
              left++;
          }

          //左指针停止移动，此时右指针指向的数应该已经无效
          if (left < right) array[right] = array[left];
      }

      //排序结束，把pivot归位
      array[left] = pivotNum;

      //返回左指针或者右指针
      return left;
  }

归并排序

基于分治策略，操作类似完全二叉树的后续遍历。
思路：将数组不断二分，知道得到长度为 1 的有序数列，然后归并有序数列
实现：通过递归，不断二分，左右指针重合，即长度为 1 时，不再二分，开始归并，归并通过双指针，比较两边有序数列的最小位，将更小的一遍填入临时数组，并后移对应边的指针，继续比较，当任一指针到达其数组的尾部，结束比较，将剩余部分直接全部分配的临时数组，最后将临时数组的值，分配给原数组
归并排序对链表排序有优势，因为可以将一些需要分配临时空间的操作省去，减少空间复杂度

• 数据

  平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	算法稳定性
  $O(n log n)$	$O(n log n)$	$O(n log n)$	$O(n)$	稳定

• 代码

public void MergeSort(int[] array, int left, int right)
   {
       //如果长度已经到达1，已经是有序状态了，就直接返回
       if (left >= right) return;
       //如果长度大于1，则二分并排序
       int mid = (right + left) / 2;

       MergeSort(array, left, mid); //左半边
       MergeSort(array, mid + 1, array.Length - 1); //右半边

       //经过二分得到两边都是有序数列，开始归并
       Merge(array, left, right);
   }

   //归并
   private void Merge(int[] array, int left, int right)
   {
       int i = left; //左半边指针
       int mid = (left + right) / 2; //中间指针
       int j = mid + 1; //右半边指针
       int length = right - left + 1; //数组长度
       int[] temp = new int[length]; //创建一个临时数组
       int t = 0; //临时数组的指针

       while (i <= mid && j <= right)
       {
           //一次比较两个数组中最小的数，并赋值给临时数组
           if (array[i] <= array[j])
           {
               temp[t++] = array[i++];
           }

           if (array[i] > array[j])
           {
               temp[t++] = array[j++];
           }
       }

       //将左半边剩余的数复制给临时数组
       while (i <= mid)
       {
           temp[t++] = array[i++];
       }

       //将右半边剩余的值复制给临时数组
       while (j <= right)
       {
           temp[t++] = array[j++];
       }

       //将临时数组的值复制给目标数组
       t = 0;
       i = left;
       while (t < length)
       {
           array[i++] = temp[t++];
       }
   }

非比较排序