快速排序算法(Quicksort)

快速排序算法是对集合中元素进行排序最通用的算法，俗称快排，其算法的时间复杂度为O(nlgn)，空间复杂度为O(1)。

我们举例来对其算法思路进行理解，譬如数组 A = { 4, 8, 1, 2, 9, 7, 3, 0, 5, 6 };

第一步，以最后一个数6为基准，把小于等于6的数挪到数组左边，把大于6的数挪到数组右边。

那么结果为 { 4, 1, 2, 3, 0, 5, 8, 9, 7, 6 }，这个时候再做一步，把8和6进行交换，得到{ 4, 1, 2, 3, 0, 5, 6, 9, 7, 8 }把6的最新位置返回。这个时候其实数组被切割成两部分，准确地说，是三部分{ 4, 1, 2, 3, 0, 5 }, { 6 }和{ 9, 7, 8 }.

第二步，对 { 4, 1, 2, 3, 0, 5 }和 { 9, 7, 8 }重复第一步的过程，我们得到

{ 4, 1, 2, 3, 0 }, { 5 }, { 7 }, { 8 }, { 9 }

第三步，再对{ 4, 1, 2, 3, 0 }进行分割，得到 { 0 }, { 1, 2, 3, 4 }

第四步，再对{ 1, 2, 3, 4 }进行分割，得到{ 1, 2, 3 }和{ 4 }

第五步，对{ 1, 2, 3 }进行分割，得到{ 1, 2 }和{ 3 }

第六步，对{ 1, 2 }进行分割，得到{ 1 }和{ 2 }

C实现代码如下

#include <stdio.h>

#define LEN 10

int partition(int *arr, int start, int end)

{

    int pivot = arr[end];

    int i = start;

    int j;

    int tmp;

    for (j = start; j < end; ++j) {

        if (arr[j] <= pivot) {

            tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

            ++i;

        }

    }

    arr[end] = arr[i];

    arr[i] = pivot;

    return i;

}

int quicksort(int *arr, int start, int end)

{

    int pivot_location;

    if (start < end) {

        pivot_location = partition(arr, start, end);

        quicksort(arr, start, pivot_location - );

        quicksort(arr, pivot_location + , end);

    }

}

int main()

{

    int i;

    int arr[LEN] = { , , , , , , , , ,  };

    quicksort(arr, , LEN - );

    for (i = ; i < LEN; ++i)

        printf("%d\n", arr[i]);

    return ;

}

Java实现代码如下

public class QuickSort {

    // Sort a list of numbers in an array within [start, end]

    public void quickSort(int[] A, int start, int end) {

        if (start < end) {

            int pivotLocation = partition(A, start, end);

            quickSort(A, start, pivotLocation - 1);

            quickSort(A, pivotLocation + 1, end);

        }

    }

    // Select A[end] as the pivot, separate the array into two parts.

    private int partition(int[] A, int start, int end) {

        int pivot = A[end];

        int i = start;

        for (int j = start; j < end; ++j) {

            if (A[j] <= pivot) {

                int tmp = A[i];

                A[i] = A[j];

                A[j] = tmp;

                ++i;

            }

        }

        A[end] = A[i];

        A[i] = pivot;

        return i;

    }

    public static void main(String[] args) {

        QuickSort q = new QuickSort();

        int[] A = { 4, 8, 1, 2, 9, 7, 3, 0, 5, 6 };

        q.quickSort(A, 0, A.length - 1);

        for (int i = 0; i < A.length; ++i) {

            System.out.println(A[i]);

        }

    }

}

巴特西

快速排序算法(Quicksort)

最新文章

热门文章