快速排序
快速排序
快速排序是一种基于分治法的排序算法，通过选择一个枢轴元素（或说参考值，从数组中选择的元素）将数组划分为子数组。
在划分数组时使小于枢轴的元素保留在左侧，大于枢轴的元素位于枢轴的右侧。每轮划分后，继续对左右子数组使用相同的方法进行划分，直持续到每个子数组都只包含一个元素。此时，元素已经排好序，将元素组合起来就是一个有序的数组。
快速排序工作流程
1.选择一个枢轴元素(参考值) 这里选数组的最右边的元素 
2.重排数组 以2为枢轴元素，重排后的数组比2小的在它左边，比2大的在它右边，如下图： 
重排过程：
-
定义一个固定索引指针指向枢轴元素，并定义两个指针(快、慢双指针)都指到左边的第1个元素索引上，然后用指针指向的元素与枢轴元素进行比较；
-
如果快指针指向的元素大于枢轴元素，就把快指针往后挪1个位置，继续下一次与枢轴元素比较，此时慢指针还保持在原来的位置上；
-
继续迭代，快指针继续不断与枢轴元素比较挪移，直到快指针指的元素小于枢轴元素，就交换快慢指针所指向的元素，交换后快、慢就都同时往后挪1位置；
-
重复 2、3这一过程，快指针元素大于枢轴元素就只挪快指针；小于枢轴元素就交换快慢指针元素并把快慢指针都往后挪；
-
直到快指针到达最后一个元素的位置；
-
最后交换枢轴元素与慢指针元素；
3.划分子数组 一次遍历交换后，以原枢轴元素为界线，再分别对左右子数组做1、2操作(即1.选择数组最右边元素作为子数组的枢轴元素；2.重排子数组)； 
左子数组划分重排过程 
右子数组划分重排过程 
复杂度
|Time Complexity|| |—|—| |Best | O(nlog n) | |Worst | O(n^2) | |Average | O(nlog n) | |Space Complexity | O(log n) | |Stability | NO |
代码实现
Swift实现
import Foundation
func quickSort(array: inout Array<Int>) {
if(array.count <= 1){
return
}
//找一个参考值base
guard let base = array.first else { return }
//分配左右两块区
var left = [Int](https://luowei.github.io/list/)
var right = [Int](https://luowei.github.io/list/)
//遍历
for i in 1 ..< array.count {
//把大于base的放到右边区块，小于等于base的放到左边区块
if array[i] > base {
right.append(array[i])
}else{
left.append(array[i])
}
}
//再分别对左区与右区的数据进行同样的划分，直全部划分完
quickSort(array: &left)
quickSort(array: &right)
//把参考值，左右两边的数据拼起来
array = left + [base] + right
}
// MARK: - 快速排序，又称划分交换排序（partition-exchange sort）
// 划分交换的方式排序更省空间
func partitionExchangeSort(array:inout [Int],low:Int,hight:Int) {
if(low < hight){
//划分出一个参考值，小于参考值放左边，大于参考值的放右边
let pi:Int = partition(array: &array, low: low, hight: hight)
//对参考值左边的列表 递归调用快排方法
partitionExchangeSort(array: &array, low: low, hight: pi - 1)
//对参考值右边的列表 递归调用快排方法
partitionExchangeSort(array: &array, low: pi + 1, hight: hight)
}
}
//划分操作:比基准值小的摆放在基准前面，比基准值大的摆在基准的后面
func partition(array:inout [Int],low:Int,hight:Int) -> Int{
//选最右边的作为基准值(参考值)
let pivot = array[hight]
//i用于指向一个更大的元素
var i = low - 1
//遍历并与参考值比较，注意这里运行了双指针技巧，i与j
// for i in low ..< hight - 1 {
for j in stride(from: low, to: hight, by: 1) {
if array[j] <= pivot {
//如果pivot值小，就把array[j]与(i+1位置)互换，相当于把j指针指的数挪到前面去，i指针指的数挪到后面
i += 1
array.swapAt(i, j)
}
}
//遍历完后，把最尾部的参考值互换到(i+1)指针指的位置，这样就保证了(i+1)前面的元素肯定是小于Pivot的，其后面的数肯定是大于Pivot的
array.swapAt(i+1, hight)
return i + 1;
}
//打印
func printQuickSort(_ array:inout [Int]){
//quickSort(array: &array)
partitionExchangeSort(array: &array, low: 0, hight: array.count-1)
print(array)
}
var arr:[Int] = [3, 2, 5, 7, 1, 5, 4, 8, 11, 0]
printQuickSort(&arr)
Python实现
# Quick sort in Python
# function to find the partition position
def partition(array, low, high):
# choose the rightmost element as pivot
pivot = array[high]
# pointer for greater element
i = low - 1
# traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# if element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
# swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# return the position from where partition is done
return i + 1
# function to perform quicksort
def quickSort(array, low, high):
if low < high:
# find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# recursive call on the left of pivot
quickSort(array, low, pi - 1)
# recursive call on the right of pivot
quickSort(array, pi + 1, high)
data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)
Java实现
// Quick sort in Java
import java.util.Arrays;
class Quicksort {
// method to find the partition position
static int partition(int array[], int low, int high) {
// choose the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse through all elements
// compare each element with pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greatr element pointed by i
i++;
// swapping element at i with element at j
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// swapt the pivot element with the greater element specified by i
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
// return the position from where partition is done
return (i + 1);
}
static void quickSort(int array[], int low, int high) {
if (low < high) {
// find pivot element such that
// elements smaller than pivot are on the left
// elements greater than pivot are on the right
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
}
// Main class
class Main {
public static void main(String args[]) {
int[] data = { 8, 7, 2, 1, 0, 9, 6 };
System.out.println("Unsorted Array");
System.out.println(Arrays.toString(data));
int size = data.length;
// call quicksort() on array data
Quicksort.quickSort(data, 0, size - 1);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
C 实现
// Quick sort in C
#include <stdio.h>
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// function to find the partition position
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap the pivot element with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// function to print array elements
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
}
C++ 实现
// Quick sort in C++
#include <iostream>
using namespace std;
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// function to print the array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// function to rearrange array (find the partition point)
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap pivot with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on righ of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// Driver code
int main() {
int data[] = {8, 7, 6, 1, 0, 9, 2};
int n = sizeof(data) / sizeof(data[0]);
cout << "Unsorted Array: \n";
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
cout << "Sorted array in ascending order: \n";
printArray(data, n);
}