南昌网站建设开发公司,大门户wordpress主题门户新闻,wordpress 评论 瀑布,网站开发报价文件1.概念
快速排序(QuickSort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分#xff0c;其中一部分记录的关键字均比另一部分记录的关键字小#xff0c;则可分别对这两部分记录继续进行排序#xff0c;以达到整个序列有序的目的。
2.算法思想描述 1.进行一次划分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序的目的。
2.算法思想描述 1.进行一次划分找一个基准(枢轴)经过一趟遍历从后往前找比基准小的记录找到往前移然后从前往后找比基准大的记录找到往后移直到以基准为中枢将序列分为两部分即基准左边的记录都小于基准右边的记录。 2.不断的将序列分为两部分分别对子序列进行一份划分直到序列不可在划分达到整个序列有序。 一次划分的思想 3.代码
#includeiostream
using namespace std;
int Partition(int* arr, int low, int high)//O(n)
{int pivot arr[low];//用子序列的第一个记录作为基准(枢轴)while (low high)//从序列的两端交替向中间扫描{//从后往前找比基准小的记录找到往前移while (low high arr[high] pivot) high--;if (low high){arr[low] arr[high];}//从前往后找比基准大的记录找到往后移while (low high arr[low] pivot) low;if (low high){arr[high--] arr[low];}}arr[low] pivot;//经过一次划分将基准数字放在他该在的位置上(即基准左边的记录都小于基准右边的记录)return low;//返回基准(枢轴)所在的位置
}void Quick(int* arr, int low, int high)//O(nlogn)
{if (low high) return;int pivot Partition(arr, low, high);//将基准进行一次划分序列分为两份Quick(arr, low, pivot - 1);//基准左边进行排序Quick(arr, pivot 1, high);//基准右边进行排序
}void QuickSort(int* arr, int len)
{Quick(arr, 0, len - 1);
}void Show(int* arr, int len)
{for (int i 0; i len; i){printf(%d , arr[i]);}printf(\n);
}int main()
{int arr[] { 9,3,12,6,7,10,5,8,21,4 };//待排序序列int len sizeof(arr) / sizeof(arr[0]);QuickSort(arr, len);printf(快速排序结果为);Show(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}
4.效率分析 时间复杂度O(nlogn) 空间复杂度O(logn) 因为递归调用栈递归了logn次 稳定性不稳定 快速排序缺点 越有序越慢空间复杂度高不稳定。 如果序列是升序或降序则快排的时间和空间复杂度高
时间复杂度O(n²) 一次排序O(n)递归调用O(n)
空间复杂度O(n) 如果画成递归树则是一颗斜树
