1、算法描述：
快速排序（Quicksort）是对冒泡排序的一种改进。
2、解答思路：
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
3、实现：
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)、时间复杂度：
时间复杂度为O(nlogn)，是一种比较快的排序方式。
2)、空间复杂度：
和冒泡排序一样，需要额外空间为常量级，故空间复杂度为O(1)。
3)、算法稳定性：
假设现有数据:[5, 3, 8, 3, 4,10, 3, 11]，这里存在3个3分别用3a，3b，3c表示这三个三。
第一次交换元素，得到：[4, 3a, 3c, 3b, 4, 10, 8, 11 ]，原序3b在3c前面，现在3c在3b前面，交换了位置，所以该算法不是稳定算法 。
