排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法:
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间 复杂度达到了 O(n?),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:
快速排序的最坏运行情况是 O(n?),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
1. 算法步骤 从数列中挑出一个元素,称为 "基准"(pivot);
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
2. 动图演示 代码实现 JavaScript 实例 function quickSort
( arr
, left
, right
) { var len
= arr.
length , partitionIndex
, left
= typeof left
!= 'number' ? 0 : left
, right
= typeof right
!= 'number' ? len
- 1 : right
; if ( left
< right
) { partitionIndex
= partition
( arr
, left
, right
) ; quickSort
( arr
, left
, partitionIndex
- 1 ) ; quickSort
( arr
, partitionIndex
+ 1 , right
) ; } return arr
; } function partition
( arr
, left
, right
) { // 分区操作 var pivot
= left
, // 设定基准值(pivot) index
= pivot
+ 1 ; for ( var i
= index
; i
<= right
; i
++ ) { if ( arr
[ i
] < arr
[ pivot
] ) { swap
( arr
, i
, index
) ; index
++; } } swap
( arr
, pivot
, index
- 1 ) ; return index
- 1 ; } function swap
( arr
, i
, j
) { var temp
= arr
[ i
] ; arr
[ i
] = arr
[ j
] ; arr
[ j
] = temp
; } function partition2
( arr
, low
, high
) { let pivot
= arr
[ low
] ; while
( low
< high
) { while
( low
< high
&& arr
[ high
] > pivot
) { -- high
; } arr
[ low
] = arr
[ high
] ; while
( low
< high
&& arr
[ low
] <= pivot
) { ++ low
; } arr
[ high
] = arr
[ low
] ; } arr
[ low
] = pivot
; return low
; } function quickSor
t2 ( arr
, low
, high
) { if ( low
< high
) { let pivot
= partition2
( arr
, low
, high
) ; quickSort2
( arr
, low
, pivot
- 1 ) ; quickSort2
( arr
, pivot
+ 1 , high
) ; } return arr
; } Python 实例 def quickSort
( arr
, left
= None , right
= None ) :
left
= 0 if not isinstance ( left
, ( int , float ) ) else left
right
= len ( arr
) -
1 if not isinstance ( right
, ( int , float ) ) else right
if left
< right:
partitionIndex
= partition
( arr
, left
, right
) quickSort
( arr
, left
, partitionIndex-
1 ) quickSort
( arr
, partitionIndex+
1 , right
) return arr
def partition
( arr
, left
, right
) :
pivot
= left
index
= pivot+
1 i
= index
while i
<= right:
if arr
[ i
] < arr
[ pivot
] :
swap
( arr
, i
, index
) index+
= 1 i+
= 1 swap
( arr
, pivot
, index-
1 ) return index-
1 def swap
( arr
, i
, j
) :
arr
[ i
] , arr
[ j
] = arr
[ j
] , arr
[ i
] Go 实例 func quickSort
( arr
[] int ) [] int { return _quickSort
( arr
, 0 , len ( arr
) - 1 ) } func _quickSort
( arr
[] int , left
, right
int ) [] int { if left < right
{ partitionIndex
:= partition
( arr
, left
, right
) _quickSort
( arr
, left
, partitionIndex
- 1 ) _quickSort
( arr
, partitionIndex
+ 1 , right
) } return arr
} func partition
( arr
[] int , left
, right
int ) int { pivot
:= left
index
:= pivot
+ 1 for i := index
; i <
= right
; i ++ { if arr
[ i ] < arr
[ pivot
] { swap
( arr
, i , index
) index
+= 1 } } swap
( arr
, pivot
, index
- 1 ) return index
- 1 } func swap
( arr
[] int , i , j
int ) { arr
[ i ], arr
[ j
] = arr
[ j
], arr
[ i ] } C++ 实例 //严蔚敏《数据结构》标准分割函数 Paritition1
( int A
[ ] ,
int low,
int high
) { int pivot
= A
[ low
] ; while ( low
< high
) { while ( low
< high
&& A
[ high
] >= pivot
) { -- high
; } A
[ low
] = A
[ high
] ; while ( low
< high
&& A
[ low
] <= pivot
) { ++ low
; } A
[ high
] = A
[ low
] ; } A
[ low
] = pivot
; return low
; } void QuickSort
( int A
[ ] ,
int low,
int high
) //快排母函数 { if ( low
< high
) { int pivot
= Paritition1
( A, low, high
) ; QuickSort
( A, low, pivot
- 1 ) ; QuickSort
( A, pivot
+ 1 , high
) ; } } Java 实例 public class QuickSort
implements IArraySort
{ @Override
public int [ ] sort
( int [ ] sourceArray
) throws Exception { // 对 arr 进行拷贝,不改变参数内容 int [ ] arr
= Arrays .
copyOf ( sourceArray, sourceArray.
length ) ; return quickSort
( arr,
0 , arr.
length - 1 ) ; } private int [ ] quickSort
( int [ ] arr,
int left,
int right
) { if ( left
< right
) { int partitionIndex
= partition
( arr, left, right
) ; quickSort
( arr, left, partitionIndex
- 1 ) ; quickSort
( arr, partitionIndex
+ 1 , right
) ; } return arr
; } private int partition
( int [ ] arr,
int left,
int right
) { // 设定基准值(pivot) int pivot
= left
; int index
= pivot
+ 1 ; for ( int i
= index
; i
<= right
; i
++ ) { if ( arr
[ i
] < arr
[ pivot
] ) { swap
( arr, i, index
) ; index
++; } } swap
( arr, pivot, index
- 1 ) ; return index
- 1 ; } private void swap
( int [ ] arr,
int i,
int j
) { int temp
= arr
[ i
] ; arr
[ i
] = arr
[ j
] ; arr
[ j
] = temp
; } } PHP 实例 function quickSort
( $arr ) { if ( count ( $arr ) <= 1 ) return $arr ; $middle = $arr [ 0 ] ; $leftArray = array ( ) ; $rightArray = array ( ) ; for ( $i = 1 ; $i < count ( $arr ) ; $i ++ ) { if ( $arr [ $i ] > $middle ) $rightArray [ ] = $arr [ $i ] ; else $leftArray [ ] = $arr [ $i ] ; } $leftArray = quickSort
( $leftArray ) ; $leftArray [ ] = $middle ; $rightArray = quickSort
( $rightArray ) ; return array_merge ( $leftArray , $rightArray ) ; } C 实例 typedef struct _Range
{ int start
, end
; } Range
; Range new_Range
( int s
, int e
) { Range r
; r.
start = s
; r.
end = e
; return r
; } void swap
( int * x
, int * y
) { int t
= * x
; * x
= * y
; * y
= t
; } void quick_sort
( int arr
[ ] , const int len
) { if ( len
<= 0 ) return ; // 避免len等於負值時引發段錯誤(Segment Fault) // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素 Range r
[ len
] ; int p
= 0 ; r
[ p
++ ] = new_Range
( 0 , len
- 1 ) ; while ( p
) { Range range
= r
[ -- p
] ; if ( range.
start >= range.
end ) continue ; int mid
= arr
[ ( range.
start + range.
end ) / 2 ] ; // 選取中間點為基準點 int left
= range.
start , right
= range.
end ; do { while ( arr
[ left
] < mid
) ++ left
; // 檢測基準點左側是否符合要求 while ( arr
[ right
] > mid
) -- right
; //檢測基準點右側是否符合要求 if ( left
<= right
) { swap
( & arr
[ left
] , & arr
[ right
] ) ; left
++; right
--; // 移動指針以繼續 } } while ( left
<= right
) ; if ( range.
start < right
) r
[ p
++ ] = new_Range
( range.
start , right
) ; if ( range.
end > left
) r
[ p
++ ] = new_Range
( left
, range.
end ) ; } } 递归法
实例 void swap
( int * x
, int * y
) { int t
= * x
; * x
= * y
; * y
= t
; } void quick_sort_recursive
( int arr
[ ] , int start
, int end
) { if ( start
>= end
) return ; int mid
= arr
[ end
] ; int left
= start
, right
= end
- 1 ; while ( left
< right
) { while ( arr
[ left
] < mid
&& left
< right
) left
++; while ( arr
[ right
] >= mid
&& left
< right
) right
--; swap
( & arr
[ left
] , & arr
[ right
] ) ; } if ( arr
[ left
] >= arr
[ end
] ) swap
( & arr
[ left
] , & arr
[ end
] ) ; else left
++; if ( left
) quick_sort_recursive
( arr
, start
, left
- 1 ) ; quick_sort_recursive
( arr
, left
+ 1 , end
) ; } void quick_sort
( int arr
[ ] , int len
) { quick_sort_recursive
( arr
, 0 , len
- 1 ) ; } C++ 函数法
sort(a,a + n);// 排序a[0]-a[n-1]的所有数. 迭代法
实例 // 参考:http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/ struct Range
{ int start, end
; Range
( int s
= 0 ,
int e
= 0 ) { start
= s, end
= e
; } } ; template < typename T
> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能 void quick_sort
( T arr
[ ] ,
const int len
) { if ( len
<= 0 ) return ; // 避免len等於負值時宣告堆疊陣列當機 // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素 Range r
[ len
] ; int p
= 0 ; r
[ p
++ ] = Range
( 0 , len
- 1 ) ; while ( p
) { Range range
= r
[ -- p
] ; if ( range.
start >= range.
end ) continue ; T mid
= arr
[ range.
end ] ; int left
= range.
start , right
= range.
end - 1 ; while ( left
< right
) { while ( arr
[ left
] < mid
&& left
< right
) left
++ ; while ( arr
[ right
] >= mid
&& left
< right
) right
-- ; std
:: swap ( arr
[ left
] , arr
[ right
] ) ; } if ( arr
[ left
] >= arr
[ range.
end ] ) std
:: swap ( arr
[ left
] , arr
[ range.
end ] ) ; else left
++ ; r
[ p
++ ] = Range
( range.
start , left
- 1 ) ; r
[ p
++ ] = Range
( left
+ 1 , range.
end ) ; } } 递归法
实例 template < typename T
> void quick_sort_recursive
( T arr
[ ] ,
int start,
int end
) { if ( start
>= end
) return ; T mid
= arr
[ end
] ; int left
= start, right
= end
- 1 ; while ( left
< right
) { //在整个范围内搜寻比枢纽元值小或大的元素,然后将左侧元素与右侧元素交换 while ( arr
[ left
] < mid
&& left
< right
) //试图在左侧找到一个比枢纽元更大的元素 left
++ ; while ( arr
[ right
] >= mid
&& left
< right
) //试图在右侧找到一个比枢纽元更小的元素 right
-- ; std
:: swap ( arr
[ left
] , arr
[ right
] ) ; //交换元素 } if ( arr
[ left
] >= arr
[ end
] ) std
:: swap ( arr
[ left
] , arr
[ end
] ) ; else left
++ ; quick_sort_recursive
( arr, start, left
- 1 ) ; quick_sort_recursive
( arr, left
+ 1 , end
) ; } template < typename T
> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能 void quick_sort
( T arr
[ ] ,
int len
) { quick_sort_recursive
( arr,
0 , len
- 1 ) ; } 参考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
以下是热心网友对快速排序算法的补充,仅供参考:
热心网友提供的补充1:
上方没有C#实现,我补充一下,如下所示:
//快速排序(目标数组,数组的起始位置,数组的终止位置)static void QuickSort(int[] array, int left = 0, int right = -1){ if (right.Equals(-1)) right = array.Length - 1; try { int keyValuePosition; //记录关键值的下标 //当传递的目标数组含有两个以上的元素时,进行递归调用。(即:当传递的目标数组只含有一个元素时,此趟排序结束) if (left < right) { keyValuePosition = Partion(array, left, right); //获取 关键值的下标(快排的核心) QuickSort(array, left, keyValuePosition - 1); //递归调用,快排划分出来的左区间 QuickSort(array, keyValuePosition + 1, right); //递归调用,快排划分出来的右区间 } } catch (Exception ex) { Console.WriteLine("Exception: {0}", ex); }}///快速排序的核心部分:确定关键值在数组中的位置,以此将数组划分成左右两区间,关键值游离在外。(返回关键值应在数组中的下标)static int Partion(int[] array, int left, int right){ int leftIndex = left; //记录目标数组的起始位置(后续动态的左侧下标) int rightIndex = right; //记录目标数组的结束位置(后续动态的右侧下标) int keyValue = array[left]; //数组的第一个元素作为关键值 int temp; //当 (左侧动态下标 == 右侧动态下标) 时跳出循环 while (leftIndex < rightIndex) { while (leftIndex < rightIndex && array[leftIndex] <= keyValue) //左侧动态下标逐渐增加,直至找到大于keyValue的下标 { leftIndex++; } while (leftIndex < rightIndex && array[rightIndex] > keyValue) //右侧动态下标逐渐减小,直至找到小于或等于keyValue的下标 { rightIndex--; } if (leftIndex < rightIndex) //如果leftIndex < rightIndex,则交换左右动态下标所指定的值;当leftIndex==rightIndex时,跳出整个循环 { temp = array[leftIndex]; array[leftIndex] = array[rightIndex]; array[rightIndex] = temp; } } //当左右两个动态下标相等时(即:左右下标指向同一个位置),此时便可以确定keyValue的准确位置 temp = keyValue; if (temp < array[rightIndex]) //当keyValue < 左右下标同时指向的值,将keyValue与rightIndex - 1指向的值交换,并返回rightIndex - 1 { array[left] = array[rightIndex - 1]; array[rightIndex - 1] = temp; return rightIndex - 1; } else //当keyValue >= 左右下标同时指向的值,将keyValue与rightIndex指向的值交换,并返回rightIndex { array[left] = array[rightIndex]; array[rightIndex] = temp; return rightIndex; }} 热心网友提供的补充2:
补充 scala 实现版本:
/** * @Auther: huowang * @Date: 19:34:47 2020/12/10 * @DES: 分区交换算法(快速排序发) * @Modified By: */object PartitionExchange { /** * 分区内切割 * @param arr * @param left * @param right * @return */ def partition(arr:Array[Int],left:Int,right: Int):Int={ // 获取基准元素 直接选取最右侧一个元素为基准元素 val pv=arr(right) // 把最左边一个索引作为堆叠索引 var storeIndex=left //操作数组 -1是因为 最右边一个元素是基准元素 for (i <- left to right-1 ){ if(arr(i)<=pv){ //把小于基准元素的元素 都堆到集合左端 swap(arr,storeIndex,i) // 把用于堆叠索引往前移动一个 storeIndex=storeIndex+1 } //如果出现了比基准元素大的元素,那么则不会移动堆叠索引 // 但是如果之后又出现了比基准元素小的元素,那边会与这个大的元素交换位置 // 进而使大的元素永远出现在堆叠索引右侧 } // 这里最有右的元素,其实是基准元素,我们把基准元素和最后堆叠索引对应的元素调换位置 // 这样基准元素左边就都是大于它的元素了 swap(arr,right,storeIndex) // 返回堆叠索引位置,目前堆叠索引指向的就是基准元素 storeIndex }def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={ if(right>left){ // 左右索引不重合 // 随便选择一个元素作为基准 就选择最左边的吧 var pivotIndex=0 // 切割返回基准元素 pivotIndex= partition(arr,left,right) // 递归对切割形成的两个子集进行排序 quicksort(arr,left,pivotIndex-1) quicksort(arr,pivotIndex,right) } arr } /** * 调换 a b 元素在数组中的位置 * @param arr * @param a * @param b */ def swap(arr:Array[Int],a:Int,b:Int)={ val tmp=arr(a) arr(a)=arr(b) arr(b)=tmp }def main(args: Array[String]): Unit = { // 测试 val arr=Array(5, 2, 9,11,3,6,8,4,0,0) val arrNew=quicksort(arr,0,arr.size-1) println(arrNew.toList.mkString(",")) }} 热心网友提供的补充3:
补充一下迭代法的 python 实现:
def _partition(array:list, start:int, end:int) -> int: """ 将数组指定片段进行左右划分,首先选择中位元素为中值。 比中位元素小的置于其左,与中位元素相等或比中位元素大的置于其右, 最后返回中位元素的下标位置。 """ # 以中位元素为中值划分,尽量避免极端情况 mid = (start + end) >> 1 array[start], array[mid] = array[mid], array[start] # 划分的实现 i, j = start, end x = array[start] while (i < j): if (i < j and array[j] >= x): j -= 1 array[i] = array[j] if (i < j and array[i] < x): i += 1 array[j] = array[i] array[i] = x return idef quickSort(array:list) -> list: """ 迭代法快速排序,队列结构辅助实现。 """ sorted_array = array.copy() length = len(sorted_array) # 使用队列保存每次划分的二元组:(起始下标,终止下标) queue = [] queue.append((0, length - 1)) # 队列为空,则所有划分操作执行完毕 while len(queue): left, right = queue.pop(0) pos = _partition(sorted_array, left, right) # 默认长度为 1 的序列有序,那么区间长度 > 1 才需要划分,才需要保存到队列中 if (left < pos - 1): queue.append((left, pos - 1)) if (pos + 1 < right): queue.append((pos + 1, right)) return sorted_arrayif __name__ == "__main__": array = [21, -17, 1, -27, 41, 17, -5, -49] sorted_array = quickSort(array) print("排序前:{array1}排序后:{array2}".format(array1=array, array2=sorted_array)) 以上为快速排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括:
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。
关于稳定性
稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
名词解释:
n:数据规模
k:"桶"的个数
In-place:占用常数内存,不占用额外内存
Out-place:占用额外内存
稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同