算法分析之快速排序算法，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;

}