一.快速排序的基本思想:通过一轮的排序将序列分割成独立的两部分，其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较次数，降低了排序时间。
二.快排的平均运行时间复杂度是:O(nlog(n))。快速排序最坏的时间复杂度是O(n^2）== 冒泡排序最坏时间复杂度也是O(O^2)。
三.3种实现方法
①固定基准元法
【如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。
因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为Θ(n^2)。
而且，输入的数据是有序或部分有序的情况是相当常见的。因此，使用第一个元素作为基准元是非常糟糕的，应该立即放弃这种想法。】
②随机基准元
【这是一种相对安全的策略。
由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。
在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。
实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。
所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度】
③三数取中【引入的原因：虽然随机选取基准时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），
要缓解这种情况，就引入了三数取中选取基准。】
四.总结分析：
最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。
可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。
事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。
显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约5%的比较次数。
五.补充总结
下面代码中 arry[left]可以换为arry[left+(right-left)/2]
实质也就是三值取中法，时间复杂度相对比arry[left]会减少很多。
下面是一个1000个随机的数，可以作为参考数据。
java版快速排序
import java.util.Arrays;
public class quickSortAlgorithm1 {
public static void main(String[] args){
long startTime = System.currentTimeMillis(); //获取开始时间
int[] num={1244,1060,1826,1976,230,68,169,735,2089,1533,1914,186,1714,1764,1931,2089,1468,36,109,1518,1588,1068,648,153,1530,1231,584,1009,1685,97,138,1274,181,1706,186,1440,648,1346,415,1596,1593,2012,1125,1322,927,534,39,1051,821,1700,711,1783,401,704,1759,848,226,1668,1514,1630,1847,1029,53,1214,1316,1155,1194,665,1569,1063,1442,1388,1775,287,1949,1608,1172,430,118,255,866,1687,450,2135,203,1975,1951,62,743,808,1658,178,1855,1303,1953,626,814,872,1427,601,529,287,1706,2136,109,158,1989,260,436,1245,1984,302,1382,1437,2012,116,944,247,1377,590,1030,1236,710,880,214,1802,1996,602,1577,1012,1340,204,1519,194,237,862,1006,543,819,1830,1709,835,1902,1271,1744,1794,1061,1890,2050,1351,1892,901,199,1612,1091,891,74,584,545,1966,1645,1303,2075,1480,942,1572,462,1598,1263,217,920,1060,943,917,680,1805,1845,1582,222,522,354,4,1476,345,765,1194,388,1981,1058,1684,427,1320,561,493,1942,79,455,1818,429,677,496,1749,1605,1515,2116,290,1901,1553,1695,1305,245,937,1764,989,219,1408,1554,1816,1378,392,1553,1084,1173,382,1782,1180,2002,767,436,344,1924,1691,49,1670,1812,862,578,641,1497,1542,215,1018,969,617,1088,1529,241,2014,1599,1810,2040,463,1304,1223,1704,605,433,1029,1223,1414,808,207,1309,1199,1106,694,2058,1733,972,146,433,596,1198,382,771,497,1877,92,1043,1628,305,1427,1349,810,2004,992,287,1136,1404,1456,1212,1609,2135,613,1923,393,118,2132,497,1746,656,190,58,488,1303,1583,534,673,920,779,1644,1388,961,1966,856,1049,1683,176,919,1786,1818,1149,1471,588,1860,804,626,1909,815,1985,868,71,1535,284,962,1085,3,11,1325,1039,1717,542,877,384,110,166,486,690,1758,1754,790,121,1415,1851,853,1927,736,260,1279,1761,115,1066,2146,343,236,1129,182,1993,997,1441,1513,1531,894,1882,1675,1118,1018,906,1549,159,622,1608,229,808,2044,1951,330,1724,668,1547,1527,1123,163,1530,912,600,249,740,2122,2098,793,1861,1605,166,358,1807,1859,1588,408,1628,269,785,445,300,2060,564,1722,1339,1050,2066,1414,36,669,1875,431,268,528,939,938,1311,1816,1290,974,1676,1154,1862,115,1238,296,2004,1720,1720,1823,1088,1640,1824,1769,1392,138,646,176,1504,298,459,544,1711,1138,507,464,1555,1105,1045,1859,103,970,1426,1029,838,339,1009,777,1715,541,452,367,522,1549,714,1679,527,1680,1608,1375,104,1978,1246,1001,243,1167,1146,1484,165,906,1858,1913,1533,733,2141,1704,709,1938,1036,1023,1578,159,1088,1970,2022,1625,487,1057,1881,487,1231,2036,833,74,1146,2040,1442,473,62,511,922,1876,361,258,2124,1178,232,1378,992,1754,1043,1359,1112,1643,1508,1941,774,664,2047,663,670,1280,1130,111,816,1534,1370,1341,1608,110,1241,1449,37,560,1311,309,1591,1490,1549,1334,852,116,250,43,951,639,570,500,23,696,322,1045,611,1928,1354,362,403,100,1544,228,689,1715,1338,1616,897,436,1621,798,1596,187,2105,1052,524,1145,987,849,19,1639,103,1826,1987,1576,857,1792,1922,1617,1170,1022,2113,1172,1215,901,1801,1883,1583,1313,379,1206,1439,721,145,1059,1366,1961,1719,554,1724,2048,1564,317,11,1589,816,137,1787,581,985,1605,1304,697,1613,2074,235,921,1111,1032,1095,2002,1582,2126,1473,632,1849,1973,171,1411,568,1908,112,1712,463,515,1697,1832,1431,1592,181,1140,1004,328,219,1873,1352,2,823,1136,2077,126,1005,2058,2028,1520,1624,1277,1461,423,1322,1871,45,1190,1015,819,13,700,1880,25,975,725,2011,18,1538,950,1529,1240,13,767,1003,1398,601,550,53,133,965,754,1248,1006,1359,664,1404,1652,1440,1442,978,328,1316,1926,1707,1385,1970,2121,2031,588,377,443,406,940,611,1173,2013,876,1358,303,1211,500,242,1078,1383,525,1287,1913,355,349,573,1784,72,1277,1550,1059,778,863,1931,755,1318,400,1884,749,854,244,1123,518,576,1419,1430,377,1922,1375,390,743,1209,719,1718,966,566,921,2100,357,1745,531,128,1354,1561,386,239,2048,1963,1789,472,467,374,255,981,996,1118,1398,95,1686,1845,46,1929,251,240,770,1424,2041,855,1766,1273,679,1793,986,812,1205,898,1658,1332,1288,1346,1219,384,1762,52,1701,916,1344,162,1873,777,208,1809,25,1080,907,1033,1317,1911,1620,638,1272,787,639,1955,1294,1230,1229,1247,1759,1982,1206,1896,827,177,636,724,1426,1945,2112,459,2072,1302,502,1074,2031,1251,1024,1530,611,2122,457,141,541,1437,1280,1385,1593,2042,523,238,90,695,1947,1870,2099,1343,1953,2089,1228,1210,2097,1664,796,201,1730,776,1399,756,1877,843,1837,639,1551,91,1164,410,788,253,1346,15,263,612,1691,1382,82,1881,1175,1101,798,1368,551,143,1586,1891,1562,1456,1066,608,1885,671,1239,584,301,1082,1135,1046,1906,1475,1934,473,1224,1642,1815,495,695,1492,479,767,874,1529,1331,1245,991,842,71,1622,1548,577,228,679,748,684,1591,1519,201,1518,1967,392,597,137,951,1081,1883,737,1935,1810,2080,97,1637,1985,421,426,1925,911,101,683,651,1299,1604,1319};
//int[] num={6,1,2,7,9,3,4,5,10,8};
SortUtils.quickSort(num, 0, num.length-1);
System.out.println(Arrays.toString(num));
long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间：" + (endTime - startTime) + "ms"); //输出程序运行时间
}
}
class SortUtils{
public static void quickSort(int arry[],int left,int right) {
if(left>=right) {//当递归到left（初始值是0）都大于right（初始值是数组长度减一）时候，返回这个数组
return;
}
// 【重大提醒：基准数的选取对算法的复杂度影响很大，这里采用三值取中法。随机数法看人品。最糟糕就是取第一个数为基准数。】具体见上面特别分析
int p=arry[left];//基准数，后面p等价于数组最左边的数
int i=left,j=right;//i是最左边的数的下标，j是最右边的数的下标
while(i!=j) {//当i不等于j时候，循环下面的操作，也就是说 当i和j相等即相遇的时候，跳出来。
while(arry[j]>=p&&i<j) {//当数组的第j个下标的数大于基准数时（i必须小于j）
j--;//j减减
}
while(arry[i]<=p&&i<j) {//当数组的第i个小标的数小于基准数时（i必须小于j）
i++;//i加加
}
//经过上面的操作数组i和j的下标的数都已经各自大于基准数和小于基准数
if(i<j) { //这个时候，就要交换这两个下标的数
int temp=arry[i];//交换两个数
arry[i]=arry[j];
arry[j]=temp;
}
}
//实质是以6位基准数的最后一次交换数字，之后以这个基准数的左边和右边分别递归。
arry[left]=arry[i];//交换基准数1
arry[i]=p;//交换基准数2
quickSort(arry, left, i-1);//选择这个数组原来的基准数的左边进行递归。
quickSort(arry, i+1, right);//选择这个数组原来的基准数的右边进行递归。
}
}
C/C++语言版快速排序
#include <stdio.h>
#include <stdlib.h>
//int a[10]={6,1,2,9,7,4,5,10,8};//1.首先全局变量定义一个数组
int a[1000]={1244,1060,1826,1976,230,68,169,735,2089,1533,1914,186,1714,1764,1931,2089,1468,36,109,1518,1588,1068,648,153,1530,1231,584,1009,1685,97,138,1274,181,1706,186,1440,648,1346,415,1596,1593,2012,1125,1322,927,534,39,1051,821,1700,711,1783,401,704,1759,848,226,1668,1514,1630,1847,1029,53,1214,1316,1155,1194,665,1569,1063,1442,1388,1775,287,1949,1608,1172,430,118,255,866,1687,450,2135,203,1975,1951,62,743,808,1658,178,1855,1303,1953,626,814,872,1427,601,529,287,1706,2136,109,158,1989,260,436,1245,1984,302,1382,1437,2012,116,944,247,1377,590,1030,1236,710,880,214,1802,1996,602,1577,1012,1340,204,1519,194,237,862,1006,543,819,1830,1709,835,1902,1271,1744,1794,1061,1890,2050,1351,1892,901,199,1612,1091,891,74,584,545,1966,1645,1303,2075,1480,942,1572,462,1598,1263,217,920,1060,943,917,680,1805,1845,1582,222,522,354,4,1476,345,765,1194,388,1981,1058,1684,427,1320,561,493,1942,79,455,1818,429,677,496,1749,1605,1515,2116,290,1901,1553,1695,1305,245,937,1764,989,219,1408,1554,1816,1378,392,1553,1084,1173,382,1782,1180,2002,767,436,344,1924,1691,49,1670,1812,862,578,641,1497,1542,215,1018,969,617,1088,1529,241,2014,1599,1810,2040,463,1304,1223,1704,605,433,1029,1223,1414,808,207,1309,1199,1106,694,2058,1733,972,146,433,596,1198,382,771,497,1877,92,1043,1628,305,1427,1349,810,2004,992,287,1136,1404,1456,1212,1609,2135,613,1923,393,118,2132,497,1746,656,190,58,488,1303,1583,534,673,920,779,1644,1388,961,1966,856,1049,1683,176,919,1786,1818,1149,1471,588,1860,804,626,1909,815,1985,868,71,1535,284,962,1085,3,11,1325,1039,1717,542,877,384,110,166,486,690,1758,1754,790,121,1415,1851,853,1927,736,260,1279,1761,115,1066,2146,343,236,1129,182,1993,997,1441,1513,1531,894,1882,1675,1118,1018,906,1549,159,622,1608,229,808,2044,1951,330,1724,668,1547,1527,1123,163,1530,912,600,249,740,2122,2098,793,1861,1605,166,358,1807,1859,1588,408,1628,269,785,445,300,2060,564,1722,1339,1050,2066,1414,36,669,1875,431,268,528,939,938,1311,1816,1290,974,1676,1154,1862,115,1238,296,2004,1720,1720,1823,1088,1640,1824,1769,1392,138,646,176,1504,298,459,544,1711,1138,507,464,1555,1105,1045,1859,103,970,1426,1029,838,339,1009,777,1715,541,452,367,522,1549,714,1679,527,1680,1608,1375,104,1978,1246,1001,243,1167,1146,1484,165,906,1858,1913,1533,733,2141,1704,709,1938,1036,1023,1578,159,1088,1970,2022,1625,487,1057,1881,487,1231,2036,833,74,1146,2040,1442,473,62,511,922,1876,361,258,2124,1178,232,1378,992,1754,1043,1359,1112,1643,1508,1941,774,664,2047,663,670,1280,1130,111,816,1534,1370,1341,1608,110,1241,1449,37,560,1311,309,1591,1490,1549,1334,852,116,250,43,951,639,570,500,23,696,322,1045,611,1928,1354,362,403,100,1544,228,689,1715,1338,1616,897,436,1621,798,1596,187,2105,1052,524,1145,987,849,19,1639,103,1826,1987,1576,857,1792,1922,1617,1170,1022,2113,1172,1215,901,1801,1883,1583,1313,379,1206,1439,721,145,1059,1366,1961,1719,554,1724,2048,1564,317,11,1589,816,137,1787,581,985,1605,1304,697,1613,2074,235,921,1111,1032,1095,2002,1582,2126,1473,632,1849,1973,171,1411,568,1908,112,1712,463,515,1697,1832,1431,1592,181,1140,1004,328,219,1873,1352,2,823,1136,2077,126,1005,2058,2028,1520,1624,1277,1461,423,1322,1871,45,1190,1015,819,13,700,1880,25,975,725,2011,18,1538,950,1529,1240,13,767,1003,1398,601,550,53,133,965,754,1248,1006,1359,664,1404,1652,1440,1442,978,328,1316,1926,1707,1385,1970,2121,2031,588,377,443,406,940,611,1173,2013,876,1358,303,1211,500,242,1078,1383,525,1287,1913,355,349,573,1784,72,1277,1550,1059,778,863,1931,755,1318,400,1884,749,854,244,1123,518,576,1419,1430,377,1922,1375,390,743,1209,719,1718,966,566,921,2100,357,1745,531,128,1354,1561,386,239,2048,1963,1789,472,467,374,255,981,996,1118,1398,95,1686,1845,46,1929,251,240,770,1424,2041,855,1766,1273,679,1793,986,812,1205,898,1658,1332,1288,1346,1219,384,1762,52,1701,916,1344,162,1873,777,208,1809,25,1080,907,1033,1317,1911,1620,638,1272,787,639,1955,1294,1230,1229,1247,1759,1982,1206,1896,827,177,636,724,1426,1945,2112,459,2072,1302,502,1074,2031,1251,1024,1530,611,2122,457,141,541,1437,1280,1385,1593,2042,523,238,90,695,1947,1870,2099,1343,1953,2089,1228,1210,2097,1664,796,201,1730,776,1399,756,1877,843,1837,639,1551,91,1164,410,788,253,1346,15,263,612,1691,1382,82,1881,1175,1101,798,1368,551,143,1586,1891,1562,1456,1066,608,1885,671,1239,584,301,1082,1135,1046,1906,1475,1934,473,1224,1642,1815,495,695,1492,479,767,874,1529,1331,1245,991,842,71,1622,1548,577,228,679,748,684,1591,1519,201,1518,1967,392,597,137,951,1081,1883,737,1935,1810,2080,97,1637,1985,421,426,1925,911,101,683,651,1299,1604,1319};
//2.快排函数的三个实参是待快排的数组，
//该数组的最左边的下标，该数组最右边的下标。
void quickSort(int *arr,int left,int right)
{
//3.定义i为左哨兵,j为右哨兵,p为基准兵(当前数组的基准兵为当前数组的左哨兵下标的值)看下图示
//6,1,2,9,7,4,5,10,8
//基准哨兵:p
//左右哨兵:i j
int i=left,j=right,p=arr[left];
//4.左下标大于等于右下标也就是快排排好的时候
if(left>=right){
return;
}
while(i != j){
while(arr[j]>=p&&i<j){
j--;
}
while(arr[i]<=p&&i<j){
i++;
}
if(i<j){
int temp ;
temp =arr[i];
arr[i] =arr[j];
arr[j] =temp;
}
}
arr[left] =arr[i];
arr[i] = p;
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}
int main()//1.写主函数
{
int i;
quickSort(a,0,999);//调用快排函数
for (i=0;i<1000;i++){
printf("%d\n",a[i]);//输出结果，codeblock先ctrl+F11编译，再ctrl+F10运行；
}
return 0;
}
快速排序推荐阅读的博客：排名不分先后
http://developer.51cto.com/art/201403/430986.htm
https://blog.csdn.net/liuyi1207164339/article/details/50827608
https://www.cnblogs.com/surgewong/p/3381438.html
http://www.cnblogs.com/foreverking/articles/2234225.html
https://www.cnblogs.com/y3w3l/p/6444837.html
https://blog.csdn.net/liuzhenya1994/article/details/80254958
