快速排序是廣泛使用的排序演算法，它在平均情況下進行n log n比較，用於排序n個元素的陣列。快速排序演算法遵循分而治之的方法。 此演算法以下列方式處理該陣列。
將陣列的第一個索引設定為left和loc變數。 將陣列的最後一個索引設定為right變數。 即left = 0，loc = 0，en d = n?1，其中n是陣列的長度。
從陣列的右邊開始，從右到開掃描整個陣列，將陣列的每個元素與loc指向的元素進行比較。確保a[loc]小於a[right]。
loc。a[loc] > a[right]，則交換這兩個值。 然後轉到第3步。loc = right從左邊指向的元素開始，並將每個元素與變數loc指向的元素進行比較。 確保a[loc]> a [left]。
loc等於left。a[loc] < a[right]，然後交換兩個值並轉到第2步。loc = left。複雜性
| 複雜度 | 最好情況 | 平均情況 | 最壞情況 |
|---|---|---|---|
| 時間複雜度 | O(n)用於3路分割區或O(n log n)簡單分割區 | O(n log n) | O(n^2) |
| 空間複雜度 | - | - | O(log n) |
演算法
PARTITION (ARR, BEG, END, LOC)
第1步 : [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =
第2步 : 當FLAG != 1 時，重複第3步到第6步，
第3步 : 當 ARR[LOC] <=ARR[RIGHT]時，迴圈
AND LOC != RIGHT
SET RIGHT = RIGHT - 1
[結束回圈]
第4步 : IF LOC = RIGHT
SET FLAG = 1
ELSE IF ARR[LOC] > ARR[RIGHT]
ARR[LOC] 與 ARR[RIGHT] 交換
SET LOC = RIGHT
[結束IF]
第5步 : IF FLAG = 0
當 ARR[LOC] >= ARR[LEFT] AND LOC != LEFT 時，迴圈
SET LEFT = LEFT + 1
[結束回圈]
第6步 : IF LOC = LEFT
SET FLAG = 1
ELSE IF ARR[LOC] < ARR[LEFT]
ARR[LOC] 與 ARR[LEFT] 交換
SET LOC = LEFT
[IF結束]
[IF結束]
第7步 : [迴圈結束]
第8步 : 結束
演算法2
QUICK_SORT (ARR, BEG, END)
第1步 : IF (BEG < END)
CALL PARTITION (ARR, BEG, END, LOC)
CALL QUICKSORT(ARR, BEG, LOC - 1)
CALL QUICKSORT(ARR, LOC + 1, END)
[IF結束]
第2步 : 結束
使用C語言實現快速排序演算法，程式碼如下所示 -
#include <stdio.h>
int partition(int a[], int beg, int end);
void quickSort(int a[], int beg, int end);
void main()
{
int i;
int arr[10]={90,23,101,45,65,23,67,89,34,23};
quickSort(arr, 0, 9);
printf("The sorted array is: \n");
for(i=0;i<10;i++)
printf(" %d\t", arr[i]);
}
int partition(int a[], int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg;
right = end;
flag = 0;
while(flag != 1)
{
while((a[loc] <= a[right]) && (loc!=right))
right--;
if(loc==right)
flag =1;
else if(a[loc]>a[right])
{
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right;
}
if(flag!=1)
{
while((a[loc] >= a[left]) && (loc!=left))
left++;
if(loc==left)
flag =1;
else if(a[loc] <a[left])
{
temp = a[loc];
a[loc] = a[left];
a[left] = temp;
loc = left;
}
}
}
return loc;
}
void quickSort(int a[], int beg, int end)
{
int loc;
if(beg<end)
{
loc = partition(a, beg, end);
quickSort(a, beg, loc-1);
quickSort(a, loc+1, end);
}
}
執行上面範例程式碼，得到以下結果 -
The sorted array is:
23
23
23
34
45
65
67
89
90
101
使用Java語言實現快速排序演算法，程式碼如下所示 -
public class QuickSort {
public static void main(String[] args) {
int i;
int[] arr ={90,23,101,45,65,23,67,89,34,23};
quickSort(arr, 0, 9);
System.out.println("The sorted array is: \n");
for(i=0;i<10;i++)
System.out.println(arr[i]);
}
public static int partition(int a[], int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg;
right = end;
flag = 0;
while(flag != 1)
{
while((a[loc] <= a[right]) && (loc!=right))
right--;
if(loc==right)
flag =1;
elseif(a[loc]>a[right])
{
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right;
}
if(flag!=1)
{
while((a[loc] >= a[left]) && (loc!=left))
left++;
if(loc==left)
flag =1;
else if(a[loc] <a[left])
{
temp = a[loc];
a[loc] = a[left];
a[left] = temp;
loc = left;
}
}
}
return loc;
}
static void quickSort(int a[], int beg, int end)
{
int loc;
if(beg<end)
{
loc = partition(a, beg, end);
quickSort(a, beg, loc-1);
quickSort(a, loc+1, end);
}
}
}
執行上面範例程式碼，得到以下結果 -
The sorted array is:
23
23
23
34
45
65
67
89
90
101
使用C#語言實現快速排序演算法，程式碼如下所示 -
using System;
public class QueueSort{
public static void Main() {
int i;
int[] arr={90,23,101,45,65,23,67,89,34,23};
quickSort(arr, 0, 9);
Console.WriteLine("\n The sorted array is: \n");
for(i=0;i<10;i++)
Console.WriteLine(arr[i]);
}
public static int partition(int[] a, int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg;
right = end;
flag = 0;
while(flag != 1)
{
while((a[loc] <= a[right]) && (loc!=right))
right--;
if(loc==right)
flag =1;
else if(a[loc]>a[right])
{
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right;
}
if(flag!=1)
{
while((a[loc] >= a[left]) && (loc!=left))
left++;
if(loc==left)
flag =1;
else if(a[loc] <a[left])
{
temp = a[loc];
a[loc] = a[left];
a[left] = temp;
loc = left;
}
}
}
return loc;
}
static void quickSort(int[] a, int beg, int end)
{
int loc;
if(beg<end)
{
loc = partition(a, beg, end);
quickSort(a, beg, loc-1);
quickSort(a, loc+1, end);
}
}
}
執行上面範例程式碼，得到以下結果 -
The sorted array is:
23
23
23
34
45
65
67
89
90
101