前言
快速排序是面試中經(jīng)常會(huì)問到的一種排序算法岭埠，對比其他一些排序算法脆丁，快速排序的平均時(shí)間相對較少。
快速排序思想介紹
快速排序使用了分治的思想稚叹，通過一輪的排序焰薄，可以將序列分割成獨(dú)立的兩個(gè)部分，其中一部分的值均比基準(zhǔn)值小扒袖，另一部分的值均比基準(zhǔn)值大塞茅。而后針對兩部分序列再分別按照同樣的算法進(jìn)行排序，直到序列整體有序季率。
以如下序列arr為例進(jìn)行升序排序野瘦，說明快速排序的基本算法
第一個(gè)位置的值23作為基準(zhǔn)值base，從右邊開始比較飒泻，如果arr[high]>base,high前移鞭光。
arr[high]<base,arr[low]=arr[high]，然后low后移
Arr[low]<base,不交換泞遗，low后移
Arr[low]>base,arr[high]=arr[low]惰许，high前移
Arr[high]
將基準(zhǔn)數(shù)據(jù)賦值給low和high指向的同一位置，本輪比較結(jié)束史辙。然后汹买，再對23前的數(shù)據(jù)和23后面的數(shù)據(jù)佩伤，分別再按照上述算法進(jìn)行比較排序，依次類推晦毙，直到所有元素有序生巡。
快速排序的代碼實(shí)現(xiàn)
由于對各個(gè)子序列都要進(jìn)行相同算法的排序，可以采用遞歸思想實(shí)現(xiàn)快速排序
package com.qfedu.vo;
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp存儲(chǔ)基準(zhǔn)數(shù)
temp = arr[low];
while (i<j) {
//先從右邊開發(fā)判斷见妒，條件成立孤荣，high向左遞減
while (temp<=arr[j]&&i<j) {
j--;
}
arr[i]=arr[j];
//再從左邊開始，low依次向右遞增
while (temp>=arr[i]&&i<j) {
i++;
}
arr[j]=arr[i];
arr[i]=temp;
}
//遞歸調(diào)用左邊內(nèi)容進(jìn)行排序
quickSort(arr, low, j-1);
//遞歸調(diào)用右邊內(nèi)容進(jìn)行排序
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {15,23,7,87,34,56};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
總結(jié)
以上介紹的是普通快速排序徐鹤，針對快速排序垃环，還有一些改進(jìn)算法，可以進(jìn)一步提高執(zhí)行效率返敬。
