C++ 实现简单快速排序

佚名 6年前 (2019-04-24) 随笔 874人围观抢沙发百度已收录

#include<iostream>
#include <unistd.h>
using namespace std;

#define LOG(s)\
cout<<s<<endl;\

void printArray(int a[],int len)
{
    for(int i=0;i<len;i++){
        cout<<a[i]<<'\t';
    }
    cout<<endl;
}

void exchange(int a[],int f,int s){
    int tmp = a[f];
    a[f] = a[s];
    a[s] = tmp;
}

void quicksort(int a[],int low,int high)
{
    if (low > high) return;
    int i,j,tmp,t;
    i = low;
    j = high;
    tmp = a[low];
    while(i < j){
        while(tmp <= a[j] && i < j){
            j--;
        }
        while(tmp >= a[i] && i < j){
            i++;
        }
        if(i<j){
            exchange(a,i,j);
        }
    }
    exchange(a,low,i);
    printArray(a,6);
    // sleep(5.0);
    quicksort(a,low,j-1);
    quicksort(a,j+1,high);
}

int main()
{
    int a[] = {7,4,9,2,12,8};   
    quicksort(a,0,5);
    return 0;
}

快速排序可以简单的理解为二分，每次把最前面的一个数送到合适的位置，这样再递归的处理这个数分割后的两个数组，这样，假设有n个数，那么就需要把n个数送到合适的位置，就会递归的调用N次，哪怕后面的调用中已经不发生位置的交换。