排序算法5 快速排序

    下面是快速排序的代码，选取数组的最后一个值为比较的值。

 

#include <iostream>
using namespace std;

int partition(int arr[], int l, int r)
{
    int i = l - 1;
    int j = r;
    int v = arr[r];
    int tmp;

    for (; ;)
    {
        while (arr[++i] < v)
            ;
        while (v < arr[--j])
            if (j == l)
                break;
        if (i >= j)
            break;
        
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    tmp = arr[i];
    arr[i] = arr[r];
    arr[r] = tmp;
    return i;
}

void quicksort(int arr[], int l, int r)
{
    int i;
    if (r <= l)
        return;
    i = partition(arr, l, r);
    quicksort(arr, l, i-1);
    quicksort(arr, i+1, r);
}


int main()
{
    int arr[15] = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753};

    int i;
    
    cout << "Original array" << endl;
    for (i = 0; i < 15; i++)
        cout << arr[i] << " ";
    cout << endl << endl;

    
    quicksort(arr, 0, 14);

    cout << "Sorted array" << endl;
    for (i = 0; i < 15; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}