快速排序（Quick Sort）
一、算法基本思想：
解释一：
1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
解释二：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 [2] 三
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。 [2]
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 [2]
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
二、排序算法演示：
动态图展示：
三、代码展示：
C++代码：
#includeusing namespace std; void Qsort(int arr[], int low, int high){ if (high <= low) return; int i = low; int j = high; int key = arr[low]; while (true) { while (arr[i] <= key) { i++; if (i == high){ break; } } while (arr[j] >= key) { j--; if (j == low){ break; } } if (i >= j) break; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } arr[low] = arr[j]; arr[j] = key; Qsort(arr, low, j - 1); Qsort(arr, j + 1, high); } int main() { int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24}; Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1); for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << " "; } return 0; }
C语言代码:
void quickSort(int *number, int first, int last) {
int i, j, pivot;
int temp;
if (firstnumber[pivot])
j--;
if (i
Java代码：
public static int[] qsort(int arr[],int start,int end) {
int pivot = arr[start];
int i = start;
int j = end;
while (ipivot)) {
j--;
}
while ((istart) arr=qsort(arr,start,i-1);
if (j+1>
T[] quickSort(T[] targetArr,int start,int end)
{
inti=start+1,j=end;
T key=targetArr[start];
SortUtil sUtil=new SortUtil();
if(start==end)return(targetArr);
while(true)
{
while(targetArr[j].compareTo(key)>0)j--;
while(targetArr[i].compareTo(key)<0&&i=j)break;
sUtil.swap(targetArr,i,j);
if(targetArr[i]==key)
{
j--;
}else{
i++;
}
}
sUtil.swap(targetArr,start,j);
if(start>
voidquickSort(T[]targetArr,intstart,intend)
{
inti=start,j=end;
Tkey=targetArr[start];
while(ii&&targetArr[j].compareTo(key)>=0)
{
j--;
}
if(i
Python代码：
def quick_sort(data):
"""快速排序"""
if len(data) >= 2: # 递归入口及出口
mid = data[len(data)//2] # 选取基准值，也可以选取第一个或最后一个元素
left, right = [], [] # 定义基准值左右两侧的列表
data.remove(mid) # 从原始数组中移除基准值
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
# 示例：
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
四、快速排序算法性质：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
