前言:
现在同学们对“算法设计与分析快速排序实验报告”可能比较看重,同学们都想要分析一些“算法设计与分析快速排序实验报告”的相关资讯。那么小编在网摘上收集了一些关于“算法设计与分析快速排序实验报告””的相关内容,希望姐妹们能喜欢,看官们一起来学习一下吧!算法分析之快速排序算法,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;}
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。