算法导论(快速排序）

1.pivot为数组的最后一个数。
2.使用一个for循环就能完成partition部分。

Java实现：

package algorithm.sort;

import java.util.Arrays;

public class Quicksort {
    public static void main(String[] args) {
        int[] arr = {-9,78,0,23,-587,70};
        QUICKSORT(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void QUICKSORT(int[] A, int p, int r){
        if (p < r){
            int q = PARTITION(A, p, r);
            QUICKSORT(A, p, q-1);
            QUICKSORT(A, q+1, r);
        }
    }
    public static int PARTITION(int[] A, int p, int r){
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x){
                i++;
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
        int tmp = A[i + 1];
        A[i+1] = A[r];
        A[r] = tmp;
        return i+1;
    }
}

C++实现：

#include <iostream>
using namespace std;
int partition(int arr[], int point, int right){
    int x = arr[right];
    int i = point;
    for (int j = point; j < right; j++) {
        if (arr[j] <= x){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int tmp = arr[i];
    arr[i] = arr[right];
    arr[right] = tmp;
    return i;
}
void quickSort(int arr[], int point, int right){
    if (point < right){
        int q = partition(arr, point, right);
        quickSort(arr,0,q-1);
        quickSort(arr,q+1,right);
    }
}
int main(){
    int arr[] = {-9, 78, 0, 23, -587, 70};
    int length = sizeof(arr)/ sizeof(arr[0]);
    quickSort(arr,0,length-1);
    for (int i = 0; i < length; ++i) {
        cout<<arr[i]<<" ";
    }
    return 0;
}

最后

以上就是拉长小虾米为你收集整理的算法导论(快速排序）的全部内容，希望文章能够帮你解决算法导论(快速排序）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。