重生之数据结构与算法----常见排序算法(二)
简介上文中，我们讲到了选择排序，冒泡排序，插入排序，希尔排序。
都是相对比较简单的实现方式，因为它们都是以人的思维，维护一个index,将index与周围元素逐步对比。直到整个数组有序。
但越是效率高的算法，反而要越接近计算的的思维。否则非常难以突破O(N^2)的桎梏。
而接下来的几种效率高算法，则是一步一步接近计算机的思维，实现排序高效。
二叉树前序遍历：快速排序
快速排序的核心思路是：先将一个元素排好序，然后递归排序剩下的元素
这里可能难以理解，这说的是什么逼话？我们再拆解一下。
[*]在数组中随机选一个作为排序元素
^
pivot
[*]进行排序，将大于pivot的元素放右边，小于的放左边
^
pivot
[*]递归重复以上步骤，寻找新的切分元素，然后交换。
[,3,]
^ ^ ^
pivot2 pivot pivot3
[*]直到全部排序完成
根据上面的思维描述,我们可以写出一个代码框架，并将它们抽象成一颗二叉树
public void Sort(int[] arr,int left,int right)
{
if (left > right)
return;
//进行切分，并将P排好序
int p = Partition(arr, left, right);
//对左右子数
//是不是类似二叉树的前序遍历？
Sort(arr, left, p - 1);
Sort(arr, p + 1, right);
}
/// <summary>
/// 分区操作
/// </summary>
/// <param name="arr"></param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
private static int Partition(int[] arr, int left, int right)
{
// 选择最右边的元素作为基准元素
int pivot = arr;
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr <= pivot)
{
i++;
(arr, arr) = (arr, arr);
}
}
(arr, arr) = (arr, arr);
return i + 1;
}其实没什么变化，相对之前实现的优先级队列来说。只是把数组作为参数传递，实现原地排序而已。
复杂度分析
[*]时间复杂度
O(n log n) ，因为要对swim/sink要对每个元素调用
[*]空间复杂度
O(1)
[*]排序稳定性
不稳定，因为skin过程中，要将堆顶元素，与堆尾元素交换。 违背了相邻元素交换的原则，所以不稳定。
[*]原地排序
是，我们的优化过程就是为了结果原地排序的问题。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]