快排的实现

快排的基本思路就是二分法查找，算法的复杂度为O(nlogn)。

从小到大排序时，先从右往左扫描，找到比头一个字符小的字符，然后替换头一个字符，在从左向右扫描，找到一个比头一个大的字符，然后右往左的指针替换为这个值，反复寻找，直到右往左和左往右的指针相遇。这个相遇的地方就是头一个字符正确的位置，然后再将这个字符前面的字符以及后面的字符进行相同的过程得到排序好的字符串。

快排的c++实现：

#include <iostream>

#include <string>

#include <algorithm>



using namespace std;



string quick_sort(string arr,int low,int high){

    

    if(arr.size() == 1) return arr;

    else if(arr.size() == 0) return "";



    char tmp = arr[0];

    while(low < high)

    {

        while(low < high && tmp <= arr[high])

        {

            --high;

        }



        arr[low] = arr[high];



        while(low < high && tmp >= arr[low])

        {

            ++low;

        }



        arr[high] = arr[low];

    }



    return quick_sort(arr.substr(0, max(low, 0)), 0, low - 1) + tmp + quick_sort(arr.substr(low + 1, -1), 0, arr.size() - low - 2);

}



int main(){

    string arr;



    cin>>arr;



    int low  = 0;

    int high = arr.size()-1;

    

    cout<<quick_sort(arr,low,high)<<endl;



    return 0;

}

快排的java实现：

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };

        quickSort(arr, 0, arr.length - 1);

        System.out.println("排序后:");

        for (int i : arr) {

            System.out.println(i);

        }

    }



    private static void quickSort(int[] arr, int low, int high) {



        if (low < high) {

            // 找寻基准数据的正确索引

            int index = getIndex(arr, low, high);



            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序

            quickSort(arr, 0, index - 1);

            quickSort(arr, index + 1, high);

        }



    }



    private static int getIndex(int[] arr, int low, int high) {

        // 基准数据

        int tmp = arr[low];

        while (low < high) {

            // 当队尾的元素大于等于基准数据时,向前挪动high指针

            while (low < high && arr[high] >= tmp) {

                high--;

            }

            // 如果队尾元素小于tmp了,需要将其赋值给low

            arr[low] = arr[high];

            // 当队首元素小于等于tmp时,向前挪动low指针

            while (low < high && arr[low] <= tmp) {

                low++;

            }

            // 当队首元素大于tmp时,需要将其赋值给high

            arr[high] = arr[low];



        }

        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置

        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]

        arr[low] = tmp;

        return low; // 返回tmp的正确位置

    }

}