重生之数据结构与算法----常见排序算法(二)

简介

上文中，我们讲到了选择排序，冒泡排序，插入排序，希尔排序。
都是相对比较简单的实现方式，因为它们都是以人的思维，维护一个index,将index与周围元素逐步对比。直到整个数组有序。
但越是效率高的算法，反而要越接近计算的的思维。否则非常难以突破O(N^2)的桎梏。
而接下来的几种效率高算法，则是一步一步接近计算机的思维，实现排序高效。
二叉树前序遍历：快速排序

快速排序的核心思路是：先将一个元素排好序，然后递归排序剩下的元素
这里可能难以理解，这说的是什么逼话？我们再拆解一下。

• 在数组中随机选一个作为排序元素
  

1. [3,1,4,1,5,9,2,6]
2. ^
3. pivot

复制代码

• 进行排序，将大于pivot的元素放右边，小于的放左边
  

1. [1,1,2,3,4,5,9,6]
2.        ^
3.          pivot

复制代码

• 递归重复以上步骤，寻找新的切分元素，然后交换。
  

1. [[1,1,2],3,  [4,5,9,6]]
2.   ^      ^    ^
3. pivot2 pivot pivot3

复制代码

• 直到全部排序完成
  

1. [1,1,2,3,4,5,6,9]

复制代码

根据上面的思维描述,我们可以写出一个代码框架，并将它们抽象成一颗二叉树

1.         public void Sort(int[] arr,int left,int right)
2.         {
3.             if (left > right)
4.                 return;
6.             //进行切分，并将P排好序
7.             int p = Partition(arr, left, right);
9.             //对左右子数
10.             //是不是类似二叉树的前序遍历？
11.             Sort(arr, left, p - 1);
12.             Sort(arr, p + 1, right);
13.         }
14.                
15.                         /// <summary>
16.         /// 分区操作
17.         /// </summary>
18.         /// <param name="arr"></param>
19.         /// <param name="left"></param>
20.         /// <param name="right"></param>
21.         /// <returns></returns>
22.         private static int Partition(int[] arr, int left, int right)
23.         {
24.             // 选择最右边的元素作为基准元素
25.             int pivot = arr[right];
26.             int i = left - 1;
28.             for (int j = left; j < right; j++)
29.             {
30.                 if (arr[j] <= pivot)
31.                 {
32.                     i++;
33.                     (arr[i], arr[j]) = (arr[j], arr[i]);
34.                 }
35.             }
36.             (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
37.             return i + 1;
38.         }

复制代码

其实没什么变化，相对之前实现的优先级队列来说。只是把数组作为参数传递，实现原地排序而已。
复杂度分析

• 时间复杂度
  O(n log n) ，因为要对swim/sink要对每个元素调用
  
• 空间复杂度
  O(1)
  
• 排序稳定性
  不稳定，因为skin过程中，要将堆顶元素，与堆尾元素交换。 违背了相邻元素交换的原则，所以不稳定。
  
• 原地排序
  是，我们的优化过程就是为了结果原地排序的问题。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！