想要變優(yōu)秀，順其自然是不可能的
你需要做很多，花很多時(shí)間，忍耐并且堅(jiān)持。
快速排序，簡(jiǎn)稱快排，也是初級(jí)面試?yán)锩姹粏?wèn)到最多的排序算法，在普通使用情況下（數(shù)據(jù)基本無(wú)序，數(shù)據(jù)量n巨大），相對(duì)于直接插入排序，簡(jiǎn)單選擇排序，冒泡法排序，快速排序的效率都會(huì)更優(yōu)。這是由冒泡排序改進(jìn)的算法，也是一種基于交換排序的算法，但是不同于冒泡排序，冒泡排序每次只比較交換相鄰的兩個(gè)元素，每次只消除兩個(gè)元素之間的逆序，但是快速排序通過(guò)兩個(gè)相鄰或者不相鄰的元素的交換，能消除多個(gè)逆序，極大地加快排序的速度。
下面是每次進(jìn)行冒泡排序時(shí)的模式，這個(gè)過(guò)程中，因?yàn)槊看沃粫?huì)交換相鄰兩個(gè)元素的位置，所以只會(huì)修改這兩個(gè)元素的順序
相對(duì)于快速排序，一次可能消除多個(gè)逆序的情況，隨機(jī)選擇一個(gè)記錄anchor（一般選擇第一個(gè)元素），通過(guò)一趟排序把比anchor大的值放到右子表，比anchor小的值放到左子表，再對(duì)左右子表使用同樣的方式進(jìn)行劃分，直到每個(gè)子表都只有一個(gè)元素。
對(duì)于每一趟循環(huán)，首先設(shè)定low和high指向左右兩個(gè)邊界：
1、比較右邊界high和anchor的大小，如果high大于anchor的值，那么high--，如果是小于anchor的值，那么交換anchor和high的位置，如果找到了比anchor小的值，那么到達(dá)第2步
2、比較左邊界low和anchor的大小，如果low小于anchor的值，那么low++，如果是大于anchor的值，那么交換anchor和low的位置，返回第1步
3、重復(fù)第1步和第2步，直到low == high為止。
剛好碰巧第一個(gè)元素就是整個(gè)數(shù)組最小的，這里我們也看到了，要是元素最小的話，那么效率就跟普通的冒泡排序差不多一樣了。如果我們的序列一開(kāi)始就是基本有序的，快速排序算法（一次交換消除多個(gè)元素的逆序）的優(yōu)勢(shì)就不明顯了。
private static int Partition(int[] num,int low,int high){
int anchor = num[low]; //用第一個(gè)元素作為anchor
//當(dāng)low == high的時(shí)候退出循環(huán)
while(low <high){
// 如果anchor的值小于high，high左移
while(low <high && anchor < num[high]) high--;
num[low] = num[high];
// 如果anchor的值大于high，low右移
while(low < high && anchor >= num[low]) low++;
//當(dāng)前的low值大于anchor，讓low位置的值移動(dòng)anchor的位置
num[high] = num[low];
}
//跳出循環(huán)時(shí)，anchor不再移動(dòng)
num[high] = anchor;
return high;
}
private static void QuickSort(int[] num,int low,int high){
if (low < high) {
//第一趟排序后anchor的位置
int index = Partition(num, low, high);
QuickSort(num, low, index - 1);
QuickSort(num, index+1, high);
}
}
算法特點(diǎn)
最好的情況是待排序的集合無(wú)序，最壞情況帶排序集合基本有序，平均情況下的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度最好情況下為O(logn)，最壞情況為O(n)，適用于初始記錄無(wú)序，n較大的情況。
