各大排序算法的時(shí)間空間復(fù)雜度
2018-04-04 13.51.45.jpeg
定義
快速排序是由冒泡排序進(jìn)化而來(lái)。
- 在數(shù)據(jù)集之中，選擇一個(gè)元素作為"基準(zhǔn)"（pivot），一般選擇第一個(gè)或者最后一個(gè)；
- 所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。
- 對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止；
image.png
JAVA語(yǔ)言實(shí)現(xiàn)
private static void quickSort(int[] array, int left, int right) {
int pivot,temp,i,j;
if(left >= right) {
return;
}
//p就是基準(zhǔn)數(shù),這里就是每個(gè)數(shù)組的第一個(gè)
pivot = array[left];
i = left;
j = right;
while(left < right) {
//右邊當(dāng)發(fā)現(xiàn)小于pivot的值時(shí)停止循環(huán)
while(array[right] >= pivot && left < right) {
right--;
}
//這里一定是右邊開始，上下這兩個(gè)循環(huán)不能調(diào)換（下面有解析，可以先想想）
//左邊當(dāng)發(fā)現(xiàn)大于pivot的值時(shí)停止循環(huán)
while(array[left] <= pivot && left < right) {
left++;
}
temp = array[right];
array[right] = array[left];
array[left] = temp;
}
array[i] = array[left];//pivot與left值互換
array[left] = pivot;
quickSort(array,i,left); //對(duì)左邊快排
quickSort(array,left+1,j); //對(duì)右邊快排
}
public static void main(String[] args) {
int[] array = new int[]{4, 3, 2, 7, 8, 5, 1, 9, 6,1,2};
quickSort(array, 0, array.length - 1);
System.out.println("res = "+ Arrays.toString(array));
}
}
時(shí)間復(fù)雜度
- 最好情況：亂序
- 最差情況：當(dāng)序列本身就是正序或者逆序的時(shí)候，每次取的基準(zhǔn)數(shù)是最大或者最小，這樣劃分的兩個(gè)子集元素分別是
n-1和0個(gè)元素，這種情況就相當(dāng)于一個(gè)普通的冒泡排序其實(shí) - 平均情況：亂序
附上冒泡的簡(jiǎn)單JAVA版本
public static int[] popSort(int [] nums) {
for (int i =0 ;i < nums.length ;i++) {
for (int j =i+1 ;j < nums.length ;j++) {
if (nums[i] < nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
return nums;
}
