Java中實(shí)現(xiàn)

1.1、 函數(shù)編寫

  void QuickSort(int[] a) {
        Sort(a, 0, a.length - 1);
    }

  void Sort(int[] a, int low, int high) {
        int pivot;
        if (low < high) {
            pivot = Partten(a, low, high);
            Sort(a, low, pivot - 1);
            Sort(a, pivot + 1, high);
        }
    }

  int Partten(int[] a, int low, int high) {
        int pivotkey;
        pivotkey = a[low];
        while (low < high) {
            while (low < high && pivotkey <= a[high])
                high--;
            swap(a, low, high);
            while (low < high && pivotkey >= a[low])
                low++;
            swap(a, low, high);
        }
        return low;
    }

//交換排序數(shù)組中的倆個(gè)元素
    void swap(int[] a, int low, int high) {
        int temp = a[low];
        a[low] = a[high];
        a[high] = temp;
    }

1.2、 測(cè)試

        int[] a = {20, 40, 50, 30, 10, 100, 90};
        quickSort sort = new quickSort();
        sort.QuickSort(a);
        for (int i : a) {
            System.out.print(i+"\t");
        }

1.3场绿、 測(cè)試結(jié)果

image.png

C++中實(shí)現(xiàn)

2.1、 函數(shù)編寫

#include <iostream>
#define MAXSIZE 10000  /* 用于要排序數(shù)組個(gè)數(shù)最大值嫉入，可根據(jù)需要修改 */
typedef struct
{
    int r[MAXSIZE+1];   /* 用于存儲(chǔ)要排序數(shù)組焰盗，r[0]用作哨兵或臨時(shí)變量 */
    int length;         /* 用于記錄順序表的長(zhǎng)度 */
}SqList;
//交換L中數(shù)組r的下標(biāo)為i和j的值 
void swap(SqList *L,int i,int j)
{
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}
//自定義sqList輸出函數(shù)
void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[i]);
    printf("%d",L.r[i]);
    printf("\n");
}

/* 對(duì)順序表L作快速排序 */
void QuickSort(SqList *L)
{
    QSort(L,1,L->length);
}

/* 對(duì)順序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
    int pivot;
    if(low<high)
    {
        pivot=Partition(L,low,high); /*  將L->r[low..high]一分為二，算出樞軸值pivot */
        QSort(L,low,pivot-1);       /*  對(duì)低子表遞歸排序 */
        QSort(L,pivot+1,high);      /*  對(duì)高子表遞歸排序 */
    }
}

/*求出sqList中咒林，樞軸元素的位置*/
int Partition(SqList *L,int low,int high)
{
    int pivotkey;
    pivotkey=L->r[low]; /* 用子表的第一個(gè)記錄作樞軸記錄 */
    while(low<high) /*  從表的兩端交替地向中間掃描 */
    {
        while(low<high&&L->r[high]>=pivotkey)
            high--;
        swap(L,low,high);/* 將比樞軸記錄小的記錄交換到低端 */
        while(low<high&&L->r[low]<=pivotkey)
            low++;
        swap(L,low,high);/* 將比樞軸記錄大的記錄交換到高端 */
    }
    return low; /* 返回樞軸所在位置 */
}

2.2熬拒、測(cè)試

int main() {
    int n = 7;
    int a[n] = {20, 30, 50, 40, 10, 90, 35};
    SqList list;
    for (int i = 0; i < n; ++i) {
        list.r[i] = a[i];
    }
    list.length = n;
    QuickSort(&list);
    print(list);
    return 0;
}

2.3、 測(cè)試結(jié)果

image.png