Java中实现

1.1、 函数编写

  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;
    }

//交换排序数组中的俩个元素
    void swap(int[] a, int low, int high) {
        int temp = a[low];
        a[low] = a[high];
        a[high] = temp;
    }

1.2、 测试

        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、 测试结果

image.png

C++中实现

2.1、 函数编写

#include <iostream>
#define MAXSIZE 10000  /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1];   /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;         /* 用于记录顺序表的长度 */
}SqList;
//交换L中数组r的下标为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输出函数
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");
}

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
    QSort(L,1,L->length);
}

/* 对顺序表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);       /*  对低子表递归排序 */
        QSort(L,pivot+1,high);      /*  对高子表递归排序 */
    }
}

/*求出sqList中，枢轴元素的位置*/
int Partition(SqList *L,int low,int high)
{
    int pivotkey;
    pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
    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、测试

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、 测试结果

image.png