老狗啃骨头之算法-快速排序
source link: http://www.veiking.cn/blog/1022-page.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍尔（C. A. R. Hoare）的大神，沐浴斋戒，焚香祷告…..苦思冥想，终得所创
快速排序（Quick Sort）
快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍尔（C. A. R. Hoare）的大神，沐浴斋戒，焚香祷告…..苦思冥想，终得所创。
快速排序是利用分治策略，分而排之，通过一次排序操作将样本数据分割成独立的两部分，并使其中一部分所有数据值都小于另一部分；然后被分割的两部分进行递归做同样的操作，依次再分，直至排序完成。
排序算法这种涉及二分的算法，其过程一般递归进行，这在数据结构的层面上，会利用到堆栈，相对于一般线性结构算法，在特定的情况下表现出质的计算效率的提升，这也是我们学习数据结构和算法的精髓之处。
1：选一基准元素（习惯上选首尾元素，其实随机亦可）；
2：遍历对比，将小于基准元素的都放置在之前，将大于基准元素的都放置在之后（相等的可随意安置）；此时基准元素将处在其数据样本排好顺序的正确位置；
3：然后对基准元素两侧的数据，分别依次执行1～3操作，直至排序完成。
import java.util.Arrays;
/**
* @author :Veiking
* @version :2020年10月15日
* 说明 :快速排序算法
*/
public class QuickSort {
// 排序方法入口
public static int[] sort(int[] arrays) {
int begin = 0;
int end = arrays.length-1;
doSort(arrays, begin, end);
return arrays;
}
/**
* 快速排序方法主体，其核心是寻得一基准元素，小的放在前，大的放在后，将数组二分且分别依此排序
* @param arrays
* @param begin
* @param end
* @return
*/
public static int[] doSort(int[] arrays, int begin, int end) {
// 不得越界，也是数组排序处理完毕的标识
if(begin=base) {
end--;
}
// 将这个小于基准元素的值放置数组前方刚才那个放到数组尾部元素原先的位置
arrays[begin] = arrays[end];
}
// 直至遍历完毕，这个begin也已经和end重合了，把选定的基准元素放到这个位置，整个数组排序完毕后，这个元素正确的位置
arrays[begin] = base;
return begin;
}
// 执行
public static void main(String[] args) {
int[] input = new int[]{3, 6, 9, 5, 13, 15, 4, 11, 1, 12, 16, 2, 14, 10, 7, 8};
System.out.println("样本初始样本数据："+Arrays.toString(input));
int[] output = QuickSort.sort(input);
System.out.println("快速排序结果数据："+Arrays.toString(output));
}
}
)>快速排序算法的基本性能，归纳如下图：
1、 时间复杂度
快速排序之所以相对冒泡排序比较快，是因为快排两头跳跃式的遍历交换，实际上避免和减少了像冒泡那种老实巴交在相邻元素间一次又一次的逐次操作，从而在数据量大的时候，能凸显优势。
当然喝凉水也有塞牙缝的时候，遇到极端特例，每次去的基准元素，都是最小（或最大）的，这时候快速排序也会变成处理相邻数据逐个对比交换的情况，差不多跟冒泡基本一样了，最差时间复杂度跟冒泡排序一样悲催，所以最差时间复杂度是O(n2)；
当快排的每一次的操作，都能将数据样本平分的时候，递归数组的平均长度和处理深度，都接近最优，我们说快排的最优时间复杂度为O(nlog2n)；
但快排的特点是用于数据量大的时候，我们知道，一般数据样本多且复杂的时候，整体就越接近随机，越是随机，每次操作都越接近于平分，故我们把快排的最优时间复杂度，当作它的平均时间复杂度，即平均时间复杂度，也为O(nlog2n)。
不难得出结论，一般来说：数据量越大，快排的优势越明显；数据样本越随机无序，快排表现的性能越好。
2、 空间复杂度
快速排序，在实现的过程中运用了二分策略，每一次都需要开辟空间用于存储基准元素，取其平均，可以认为快速排序的空间复杂度为O(nlog2n)。
3、稳定性
在快速排序中，由于是分区跳跃式的交换，等值元素有可能会因为分区导致相对顺序不定，所以快速排序是不稳定的算法。
Recommend
-
8
插入排序，一般是说直接插入排序，是一种最直观最简单的排序算法。插入排序的原理是依次将未排序的数据元素插入已完成排序的有序数列，如此往复，最终完成所有数据的排序。在插入排序中，往前遍历的时候，遇到等值的元素就直接插入结...
-
4
简单选择排序是一种相对简单直观的基础排序算法，每一次都做简单选择，每一次都选出最大或最小。选择排序的核心思想就是：在遍历的过程中，每次都选数据样本中最小的数据，放在首位。看起来简单纯朴吧，从第一个元素开始，每次都取剩...
-
5
归并排序是一种非常典型的分治策略应用排序算法，简而概括：分而排之，合而并之。归并排序，据说是冯·诺伊曼在1945年首次提出。冯·诺伊曼，是现代计算机科学发展史上开天辟地的大佬之一，不单单是计算机领域，这哥们在整个数学、量子...
-
8
老狗啃骨头之数据结构-栈和队列_老狗啃骨头_Veiking百草园-知识点滴,日常分享 栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可...
-
4
冒泡排序是交换排序，是一种简单直观的排序算法。冒泡的算法原理是逐次循环遍历，比较两个相邻的元素，将小的（或大的）往前调。这样，每一轮都能得到一个最小的（或最大的），剩下的重复这个操作，最后完成排序。这个算法的名字，每...
-
5
老狗啃骨头之算法-排序算法总结_老狗啃骨头_Veiking百草园-知识点滴,日常分享 关于排序的算法，还有很多种。还有一些排序算法的思想，在不同的使用场景下再结合其它的算法逻辑，又可以衍生出新的算法设计。比...
-
6
基数排序是一种不在数据值本身之间比较的排序算法，而是通过数据按位数“切割”对比，从而实现排序的算法，所以基数排序也被认为是一种典型的非比较排序算法。在实际运用中，基数排序的使用场景不局限于整数，凡是整数可以表达的，或者...
-
5
天地玄黄，宇宙洪荒……千年以前，南梁周大侍郎，用一夜白头给我们留下了包罗万象又朗朗上口的童谣，得以千年唱诵，这是古人原始纯真的智慧。但浩瀚如宇宙，细微如尘沙，世间如此繁杂，计算机是搞不懂的，计算机的一零世界努力模拟，也...
-
4
老狗啃骨头之算法-八大排序算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享 排序，就是将一组无序的数据，按照一定规则，使其有序化排列。排序时是否根据比较来决定元素间的相对次序，还可以分为比较类排序...
-
5
老狗啃骨头之数据结构-小说算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享 一般说，随着数据结构复杂度和解决问题的复杂度的增长，时间复杂度也是随之增长的。在相同的资源条件下，空间复杂度和时间复杂度...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK