# 快速排序详细实现指南和实现代码解析

2021年4月2日11:51:14 发表评论 501 次浏览

## 本文概述

1. 始终选择第一个元素作为枢轴。
2. 始终选择最后一个元素作为枢轴(在下面实现)
3. 选择一个随机元素作为枢轴。
4. 选择中位数作为枢轴。

quickSort中的关键过程是partition()。分区的目标是, 给定一个数组和一个数组元素x作为枢轴, 将x放在已排序数组中的正确位置, 并将所有较小的元素(小于x)放在x之前, 并将所有较大的元素(大于x)放在之后X。所有这些都应在线性时间内完成。

``````/* low  --> Starting index, high  --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);  // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}``````

``````/* low  --> Starting index, high  --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);  // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}``````

partition()的伪代码

``````/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];

i = (low - 1)  // Index of smaller element

for (j = low; j <= high- 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++;    // increment index of smaller element
swap arr[i] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}``````

partition()的插图：

``````arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6

low = 0, high =  6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j
// are same

j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30

j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped

We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped

Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.``````

## C ++

``````/* C++ implementation of QuickSort */
#include <bits/stdc++.h>
using namespace std;

// A utility function to swap two elements
void swap( int * a, int * b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition ( int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for ( int j = low; j <= high - 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */
void quickSort( int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr`````` is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void printArray( int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " " ;
cout << endl;
}

// Driver Code
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof (arr) / sizeof (arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n" ;
printArray(arr, n);
return 0;
}

// This code is contributed by rathbhupendra``````

## C

``````/* C implementation QuickSort */
#include<stdio.h>

// A utility function to swap two elements
void swap( int * a, int * b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition ( int arr[], int low, int high)
{
int pivot = arr[high];    // pivot
int i = (low - 1);  // Index of smaller element

for ( int j = low; j <= high- 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++;    // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted, low  --> Starting index, high  --> Ending index */
void quickSort( int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr`````` is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void printArray( int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf ( "%d " , arr[i]);
printf ( "\n" );
}

// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof (arr)/ sizeof (arr[0]);
quickSort(arr, 0, n-1);
printf ( "Sorted array: \n" );
printArray(arr, n);
return 0;
}``````

## Java

``````// Java program for implementation of QuickSort
class QuickSort
{
/* This function takes last element as pivot, places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition( int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low- 1 ); // index of smaller element
for ( int j=low; j<high; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+ 1 ];
arr[i+ 1 ] = arr[high];
arr[high] = temp;

return i+ 1 ;
}

/* The main function that implements QuickSort()
arr[] --> Array to be sorted, low  --> Starting index, high  --> Ending index */
void sort( int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);

// Recursively sort elements before
// partition and after partition
sort(arr, low, pi- 1 );
sort(arr, pi+ 1 , high);
}
}

/* A utility function to print array of size n */
static void printArray( int arr[])
{
int n = arr.length;
for ( int i= 0 ; i<n; ++i)
System.out.print(arr[i]+ " " );
System.out.println();
}

// Driver program
public static void main(String args[])
{
int arr[] = { 10 , 7 , 8 , 9 , 1 , 5 };
int n = arr.length;

QuickSort ob = new QuickSort();
ob.sort(arr, 0 , n- 1 );

System.out.println( "sorted array" );
printArray(arr);
}
}
/*This code is contributed by Rajat Mishra */``````

## python

``````# Python program for implementation of Quicksort Sort

# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr, low, high):
i = ( low - 1 )         # index of smaller element
pivot = arr[high]     # pivot

for j in range (low , high):

# If current element is smaller than the pivot
if   arr[j] < pivot:

# increment index of smaller element
i = i + 1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1 ], arr[high] = arr[high], arr[i + 1 ]
return ( i + 1 )

# The main function that implements QuickSort
# arr[] --> Array to be sorted, # low  --> Starting index, # high  --> Ending index

# Function to do Quick sort
def quickSort(arr, low, high):
if low < high:

# pi is partitioning index, arr`````` is now
# at right place
pi = partition(arr, low, high)

# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi - 1 )
quickSort(arr, pi + 1 , high)

# Driver code to test above
arr = [ 10 , 7 , 8 , 9 , 1 , 5 ]
n = len (arr)
quickSort(arr, 0 , n - 1 )
print ( "Sorted array is:" )
for i in range (n):
print ( "%d" % arr[i]), # This code is contributed by Mohit Kumra``````

## C#

``````// C# program for implementation of QuickSort
using System;

class GFG {

/* This function takes last element as pivot, places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition( int []arr, int low, int high)
{
int pivot = arr[high];

// index of smaller element
int i = (low - 1);
for ( int j = low; j < high; j++)
{
// If current element is smaller
// than the pivot
if (arr[j] < pivot)
{
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swap arr[i+1] and arr[high] (or pivot)
int temp1 = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp1;

return i+1;
}

/* The main function that implements QuickSort()
arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */
static void quickSort( int []arr, int low, int high)
{
if (low < high)
{

/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);

// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}

// A utility function to print array of size n
static void printArray( int []arr, int n)
{
for ( int i = 0; i < n; ++i)
Console.Write(arr[i] + " " );

Console.WriteLine();
}

// Driver program
public static void Main()
{
int []arr = {10, 7, 8, 9, 1, 5};
int n = arr.Length;
quickSort(arr, 0, n-1);
Console.WriteLine( "sorted array " );
printArray(arr, n);
}
}

// This code is contributed by Sam007.``````

``````Sorted array:
1 5 7 8 9 10``````

QuickSort分析

``T(n) = T(k) + T(n-k-1) + (n)``

QuickSort花费的时间取决于输入阵列和分区策略。以下是三种情况。

``````T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)``````

``T(n) = 2T(n/2) + (n)``

``T(n) = T(n/9) + T(9n/10) + (n)``

QuickSort稳定吗？

a)小于枢轴的arr [l..i]元素。

b)arr [i + 1..j-1]元素等于数据透视。

c)大于枢轴的arr [j..r]元素。

• 快速排序测验
• 有关QuickSort的最新文章
• 排序的编码实践。

http://en.wikipedia.org/wiki/Quicksort