快速排序

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>

using namespace std;

void quickSort(int a[], int low, int high) {
    if (low >= high)
        return;
    int target = a[low];
    int start = low;
    int end = high;
    while (low != high) {
        while (a[high] < target && high > low) {
            high--;
        }
        if (high > low)
            a[low++] = a[high];
        while (a[low] > target && high > low) {
            low++;
        }
        if (high > low)
            a[high--] = a[low];
    }

    a[low] = target;

    quickSort(a, start, low - 1);
    quickSort(a, low + 1, end);
}


void sort(int a[], int len) {
    quickSort(a, 0, len - 1);

    for (int i = 0; i < len; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}


int _tmain(int argc, _TCHAR* argv[])
{
    int a[8] = {1, 3, 6, 9, 2, 8, 7, 12};
    sort(a, 8);
    system("pause");
    return 0;
}

在数组中找到第k大的元素

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>

using namespace std;

int findKTh(int a[], int low, int high, int k) {
    if (low >= high)
        return a[low];
    int target = a[low];
    int start = low;
    int end = high;
    while (low != high) {
        while (a[high] < target && high > low) {
            high--;
        }
        if (high > low)
            a[low++] = a[high];
        while (a[low] > target && high > low) {
            low++;
        }
        if (high > low)
            a[high--] = a[low];
    }

    a[low] = target;
    if (low == k - 1) {
        return a[low];
    } 
    else if (k - 1 < low){
        return findKTh(a, start, low - 1, k);
    }
    else {
        return findKTh(a, low + 1, end, k);
    }
}


void sort(int a[], int len) {
    int value = findKTh(a, 0, len - 1, 10);
    cout << value << endl;

    for (int i = 0; i < len; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}


int _tmain(int argc, _TCHAR* argv[])
{
    int a[10] = {1, 3, 6, 9, 2, 8, 7, 12, 25, 5};
    sort(a, 10);
    system("pause");
    return 0;
}