编辑代码

#include <iostream>
#include <math.h>
#include <cstdlib>

using namespace std;
void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void printArray1(int array[], int arrStart, int arrEnd) {
    for (int i = arrStart; i < arrEnd; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

//快速排序的核心思想就是从数组中选一个数据，然后找到这个数据在数组排序后的位置，
// 并且把比这个数小的数据放在这个位置的左边，把比这个数大的数据都放在这个位置的右边
// 然后分别对左右两边的数组采用同样的方式排序直至所有分成的两部分的数据元素为1，就都排好序了

// partition就是要找出选择的这个数据在数组排序后的位置并且把比它小的数据放在这个位置左边，比这个数据大的放在这个位置的右边

// 遍历数组，找出比基准值小的数据，从数组最左边位置开始，依次把找到的小的数据放置好 
//返回值就是分区后，基准值所在的位置 
// 该函数的功能是将比基准值小的数据放在它的左边，比它大的数据放在它的右边
// 把基准值放到它排序后的位置 

int partition(int array[], int arrStart, int arrEnd, int pivotPos) {
   int arrayLen = arrEnd - arrStart;

   if ( arrayLen < 1 || pivotPos < arrStart || pivotPos >= arrEnd) {
       cout << "Please check your implementation." << endl;
       return -1;
   }

   // 把pivotValue放到数组的最后，避免数组不连续
   int pivotValue = array[pivotPos];
   array[pivotPos] = array[arrEnd - 1];

   int i = 0; // 表示比基准值小的数据的个数

   // 查找比基准值小的数据，并从数组的最左边依次放置
   for (int j = arrStart; j < arrEnd - 1; ++j)
   {
       if (array[j] < pivotValue) {
          int temp;
          temp = array[arrStart + i];
          array[arrStart + i] = array[j];
          array[j] = temp;
          ++i;
       }
   }

   // 将基准值放到对应的位置上
   array[arrEnd - 1] = array[arrStart + i];
   array[arrStart + i] = pivotValue;

   // 基准值在数组中的位置
   return arrStart + i;
}
// 找基准值在排序前的位置
int findPivotPos(int array[], int arrStart, int arrEnd) {
    int arrLen = arrEnd - arrStart;
     // 取三个值的中值
    int mid = arrStart + arrLen/2;
    int min = arrStart;
    int max = arrEnd - 1;

    //cout <<array[min] << ":" << array[mid] << ":" << array[max] << endl;

    if (array[min] > array[mid]) {
        int temp = min;
        min = mid;
        mid = temp;
    }

    if (array[mid] > array[max]) {
        int temp = mid;
        mid = max;
        max = mid;
    }

    if (array[min] > array[mid]){
        int temp = min;
        min = mid;
        mid = temp;
    }
    return mid;

    //return arrStart; //让第一个元素作为基准值
    //return arrEnd-1; //让最后一个元素作为基准值
}
bool quickSort(int array[], int arrStart, int arrEnd) {
    int arrLen = arrEnd - arrStart;
    if (arrLen < 0) {
        cout << "Please check your input." << endl;
        return false;
    }

    if (arrLen == 0 || arrLen == 1) {
        return true;
    } 

    int pivotPos = findPivotPos(array, arrStart, arrEnd);


    int pivotOrderedPos = partition(array, arrStart, arrEnd, pivotPos);

    cout << "pos " << pivotPos << endl;
    cout << "ordered pos " << pivotOrderedPos << endl;
    printArray1(array, arrStart, pivotOrderedPos);
    printArray1(array, pivotOrderedPos, arrEnd);

    quickSort(array, arrStart, pivotOrderedPos);

    quickSort(array, pivotOrderedPos+1, arrEnd);

    return true;
}



int main(){
    int array0[] = {};
    int arrayLen = sizeof(array0)/sizeof(int);

    printArray(array0, arrayLen);
    quickSort(array0, 0, arrayLen);
    printArray(array0, arrayLen);

    cout << "=========================================" << endl;

    int array1[] = {1};
    arrayLen = sizeof(array1)/sizeof(int);

    printArray(array1, arrayLen);
    quickSort(array1, 0, arrayLen);
    printArray(array1, arrayLen);

    cout << "=========================================" << endl;

    int array2[] = {2, 1};
    arrayLen = sizeof(array2)/sizeof(int);

    printArray(array2, arrayLen);
    quickSort(array2, 0, arrayLen);
    printArray(array2, arrayLen);

    cout << "=========================================" << endl;

    int array3[] = {1, 5, 3};
    arrayLen = sizeof(array3)/sizeof(int);

    printArray(array3, arrayLen);
    quickSort(array3, 0, arrayLen);
    printArray(array3, arrayLen);


    cout << "=========================================" << endl;

    int array4[] = {9, 12, 8, 7};
    arrayLen = sizeof(array4)/sizeof(int);

    printArray(array4, arrayLen);
    quickSort(array4, 0, arrayLen);
    printArray(array4, arrayLen);

    cout << "=========================================" << endl;

    int array5[] = {11,8,3,9,7,1,2,5};
    arrayLen = sizeof(array5)/sizeof(int);

    printArray(array5, arrayLen);
    quickSort(array5, 0, arrayLen);
    printArray(array5, arrayLen);


}