各种排序算法一览

完整代码下载：https://github.com/weida-studio/Sort

1、冒泡排序

void BubbleSort::sort(){
    for (int i = count-1; i>0; i--) {
        for (int j=0; j<i; j++) {
            if (array[j] > array[j+1]) {
                swap(array[j], array[j+1]);
            }
        }
    }
}

2、选择排序

void SelectionSort::sort(){
    for (int i=count-2; i>=0; i--) {
        int maxIndex = i+1;
        for (int j=0; j<=i; j++) {
            if (array[j] > array[maxIndex]) {
                maxIndex = j;
            }
        }
        swap(array[i+1], array[maxIndex]);
    }
}

3、插入排序

void InsertSort::sort(){
    for (int i = 1; i<count; i++) {
        for (int j=i-1; j>=0; j--) {
            if (array[j] > array[j+1] ) {
                swap(array[j], array[j+1]);
            }else{
                break;
            }
        }
    }
}

4、快速排序

int QuickSort::seperator(int start, int end){
    int base = array[start];
    int left = start +1;
    int right = end;
    
    while (1) {
        while (left <= end && array[left] <= base) left++;
        while (right >= left && array[right] >= base) right--;
        
        if (right > left) {
            swap(array[left], array[right]);
        }else{
            swap(array[start], array[right]);
            break;
        }
    }
    return right;
}

void QuickSort::sort(int start, int end){
    int position = seperator(start, end);
    
    if (position > start) {
        sort(start, position-1);
    }
    
    if (position < end) {
        sort(position+1, end);
    }
}

void QuickSort::sort(){
    sort(0, count-1);
}