快速排序

快速排序是廣泛使用的排序演算法，它在平均情況下進行n log n比較，用於排序n個元素的數組。快速排序演算法遵循分而治之的方法。 此演算法以下列方式處理該數組。

1. 將數組的第一個索引設置為left和loc變數。 將數組的最後一個索引設置為right變數。 即left = 0，loc = 0，en d = n?1，其中n是數組的長度。

2. 從數組的右邊開始，從右到開掃描整個數組，將數組的每個元素與loc指向的元素進行比較。確保a[loc]小於a[right]。

   • 如果是這種情況，則繼續進行比較，直到右邊等於loc。
   • 如果a[loc] > a[right]，則交換這兩個值。 然後轉到第3步。
   • 設置，loc = right

3. 從左邊指向的元素開始，並將每個元素與變數loc指向的元素進行比較。 確保a[loc]> a [left]。

   • 如果滿足上面情況，則繼續比較，直到loc等於left。
   • a[loc] < a[right]，然後交換兩個值並轉到第2步。
   • 設置loc = left。

複雜性

演算法

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