关于c++:算法分析之快速排序算法c实现

算法剖析之疾速排序算法，c++ 实现

疾速排序算法剖析

如图所示，数组开始是无序的，从两端开始比拟，找到两头值，而后以两头值为中心点，进行分段

第一次划分

而后再从每一段中反复此操作，直到只剩下分段长度为 1 完结, 即 i >= j 则完结

实现

// # 疾速排序, 将一个数组，找到一个两头值，而后以这个两头值为核心，分段
// # 而后再从每一段中反复此操作，直到只剩下分段长度为 1 完结, 即 i >= j 则完结 
// 1.  定义一个分段函数，参数别离是 arr(待排序数组),begin(终点),end(起点)
// 2. 初始化函数值 i = begin; j = end;
// 3. 从右往左找，i 不变,j--; 如果 arr[i] > arr[j], 替换 arr[i] 和 arr[j] 的值，而后替换挪动地位，j 不变，i--;
// 4. 重复操作，直到 i >= j; 完结算法并返回 i
 
#include<iostream>
using namespace std;
// 排序算法，arr 数组，begin 终点下标，end 起点下标  
int sortArr(int arr[], int begin, int end) {
    int i = begin, j = end;
    while(i < j) {while(i < j && arr[i] <= arr[j]) j--;
        if (i < j) {int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        while(i < j && arr[i] <= arr[j]) i++;
        if (i < j) {int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    return i;
}
// 分段办法，arr 数组，begin 终点下标，end 起点下标 
void quilckSort(int arr[], int begin, int end) {if (begin < end) {int middle = sortArr(arr, begin, end);
        quilckSort(arr, begin, middle - 1);
        quilckSort(arr, middle + 1, end);
    }
}
 
int main() {int arr[] = {0, 9, 8, 6, 1, 5, 4, 12, 15, 3, -2};
    int len = sizeof(arr) / 4;
    quilckSort(arr, 0, len - 1);
    for (int i = 0; i < len; i++) {cout<< arr[i] << " ";
    }
    return 0;
}