快速排序
- 时间复杂度：平均、最好为O(nlogn),最坏为O(n^2)
- 空间复杂度：O(nlogn)
- 稳定性：不稳定
算法分析：
- 快速排序使用了分治思想来把一个数组分成两个子数组（以数组为例）
- 快速排序从数组中选择一个元素为基准（pivot）
- 把比基准大的元素放到基准右边
- 把比基准小的放到基准左边
- 这样以基准为中心，就把原来的数组分成了两个子序列
- 基准左边大于基准的 和 基准右边小于基准的交换位置（双指针最快）
- 基准归位
- 然后把基准分开的两个子序列递归的重复上述步骤
- 最后整个数组排序完毕
动画演示：(动画来自五分钟学算法，侵删)
quickSort
C代码
void quickSort(int arr[],int left,int right) {
if (left > right) { return ; }
int i,j,tmp,pivot;
i = left;
j = right;
pivot = arr[left];
while (i != j) {
while (arr[j] >= pivot && i < j) {
j--;
}
while (arr[i] <= pivot && i < j) {
i++;
}
if (i < j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//基准归位
arr[left] = arr[i];
arr[i] = pivot;
//递归
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
OC代码
- (void)quickSort:(NSMutableArray *)arr left:(int)left right:(int)right {
if (left > right) {
return;
}
NSNumber *tmp = nil;
int i = left;
int j = right;
NSNumber *pivot = arr[left];
while (i != j) {
while ([arr[j] intValue] >= pivot.intValue && i < j) {
j--;
}
while ([arr[i] intValue] <= [pivot intValue] && i < j) {
i++;
}
if (i < j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
arr[left] = arr[i];
arr[i] = pivot;
[self quickSort:arr left:left right:i-1];
[self quickSort:arr left:i+1 right:right];
}
Swift代码
func quickSort(arr: inout [Int],left:Int,right:Int) -> Void {
if left > right { return }
var i = left,j = right
var pivot = arr[left],tmp = 0
while i != j {
while (arr[j] >= pivot && i < j) {
j -= 1
}
while (arr[i] <= pivot && i < j) {
i += 1
}
if i < j {
tmp = arr[i];
arr[i] = arr[j]
arr[j] = tmp
}
}
arr[left] = arr[i]
arr[i] = pivot
quickSort(arr: &arr, left: left, right: i-1)
quickSort(arr: &arr, left: i+1, right: right)
}
以下代码实现来源于网络，未验证
js代码实现
function quick_sort(arr,from,to){
var i = from;
var j = to;
var key = arr[from]; //标准值
if(from >= to){ //如果数组只有一个元素
return;
}
while(i < j){
while(arr[j] > key && i < j){ //从右边向左找第一个比key小的数，找到或者两个哨兵相碰，跳出循环
j--;
}
while(arr[i] <= key && i < j){ //从左边向右找第一个比key大的数，找到或者两个哨兵相碰，跳出循环,这里的=号保证在本轮循环结束前，key的位置不变，否则的话跳出循环，交换i和from的位置的时候，from位置的上元素有可能不是key
i++;
}
if(i < j){ //交换两个元素的位置
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[from] = arr[i] //
arr[i] = key;
quick_sort(arr,from,i-1);
quick_sort(arr,i+1,to);
}
Java实现
public static void sort(int[] a, int low, int high) {
if(low>=high)
return;
int i = low;
int j = high;
int key = a[i];
while (i < j) {
while (i < j && a[j] >= key)
j--;
a[i++] = a[j];
while (i < j && a[i] <= key)
i++;
a[j--] = a[i];
}
a[i] = key;
sort(a,low,i-1);
sort(a,i+1,high);
}
c++实现
void QuickSort(int array[], int start, int last) {
int i = start;
int j = last;
int temp = array[i];
if (i < j)
{
while (i < j) {
while (i < j && array[j]>=temp )
j--;
if (i < j) {
array[i] = array[j];
i++;
}
while (i < j && temp > array[i])
i++;
if (i < j) {
array[j] = array[i];
j--;
}
}
//把基准数放到i位置
array[i] = temp;
//递归方法
QuickSort(array, start, i - 1);
QuickSort(array, i + 1, last);
}
}
python实现
def quick_sort(array, left, right):
if left >= right:
return
low = left
high = right
key = array[low]
while left < right:
while left < right and array[right] > key:
right -= 1
array[left] = array[right]
while left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[right] = key
quick_sort(array, low, left - 1)
quick_sort(array, left + 1, high)
go实现
func quickSort(arr []int){
arrLen := len(arr)
if arrLen <= 1{
return
}
randNum := getRandNum(arrLen -1)
arr[randNum], arr[0] = arr[0],arr[randNum]
mid := arr[0]//取出用于比较的元素
head, tail := 0, arrLen -1
for {
for head <= tail && arr[head] < mid {
head ++
}
for tail > head && arr[tail] > mid {
tail --
}
if head > tail{
break
}
swap(arr, head,tail)
head++
tail--
}
QSortTwoWay(arr[:head])
QSortTwoWay(arr[head+1:])
}
