3、快速排序

//快速排序
void Solution:: fastSort(int *arr,int left,int right) {
    int i = left; int j = right;

    if (left > right) {
        return;
    }

    int key = arr[left];

    while (i != j) {
        while (arr[j] >= key && j > i) {
            j--;
        }

        while (arr[i] <= key && j > i) {
            i++;
        }

        //找到左边大于基准数的跟右边小于基准数的交换位置
        if (j > i) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
//        printf("快排后");
//        for (int i = 0; i < 7; i++) {
//            printf("%i,",arr[i]);
//        }
//        printf("\n");
    }
    //交换基准数
    arr[left] = arr[i];
    arr[i] = key;

//    printf("快排后");
//    for (int i = 0; i < 7; i++) {
//        printf("%i,",arr[i]);
//    }
//    printf("\n");

    fastSort(arr, left, i-1);
    fastSort(arr, i+1, right);
}