1、算法描述：
快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。
2、解答思路：
它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
3、實現(xiàn)：
Swift
class QuickSort {
//找到分割的index
func partition(array: inout [Int], left : Int, right : Int) -> Int {
var low = left
var high = right
let temp = array[low]
while low < high {
while low < high && array[high] >= temp {
high -= 1
}
array[low] = array[high]
while low < high && array[low] <= temp {
low += 1
}
array[high] = array[low]
}
array[low] = temp
print(array)
return low
}
//遞歸
func quickSort(array : inout [Int], left : Int , right : Int){
if left < right {
let mid = partition(array: &array, left: left, right: right)
quickSort(array: &array, left: left, right: mid - 1)
quickSort(array: &array, left: mid + 1, right: right)
}
}
}
let test = QuickSort()
var array = [Int](repeating: 0, count: 6)
for index in 0..<6 {
array[index] = Int(arc4random_uniform(7)) + Int(arc4random_uniform(2)) + 1
}
test.quickSort(array : &array, left: 0, right: array.count - 1)
print(array)
C語言
void quickSort(int array[], int left, int right) {
if (left>=right) {
return;
}
int low = left;
int high = right;
int temp = array[low];
while (low < high) {
while (low < high && temp <= array[high]) {
high --;
}
array[low] = array[high];
while (low < high && temp >= array[low]) {
low ++;
}
array[high] = array[low];
}
array[low] = temp;
quickSort(array, left, low - 1);
quickSort(array, low + 1, right);
}
4、分析：
1)、時間復(fù)雜度：
時間復(fù)雜度為O(nlogn)，是一種比較快的排序方式。
2)、空間復(fù)雜度：
和冒泡排序一樣，需要額外空間為常量級，故空間復(fù)雜度為O(1)。
3)、算法穩(wěn)定性：
假設(shè)現(xiàn)有數(shù)據(jù):[5, 3, 8, 3, 4,10, 3, 11]，這里存在3個3分別用3a，3b，3c表示這三個三。
第一次交換元素，得到：[4, 3a, 3c, 3b, 4, 10, 8, 11 ]，原序3b在3c前面，現(xiàn)在3c在3b前面，交換了位置，所以該算法不是穩(wěn)定算法 。
