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

评论

暂无评论