快速排序

1：快速排序的思想

    快速排序运用了分治的思想，即通过一趟排序 将序列分为两部分，根据选取的基准， 将比基准小的数放在基准前面，将比基准大的数放在的数放在基准后面；然后对两部分进行递归处理，以达到整个序列有序的状态。

2：快速排序的步骤

   （1）：选择基准 在一个待排序列中找一个 待排的数作为基准；

   （2）：分割操作 根据基准将序列分为两部分 

   （3）：将分割后的序列进行递归操作；

3：选择基准的方法

（1）：固定基准：即选取序列的第一个数或最后一个数作为基准；（耗费时间长）

（2）：三数取中：即将序列中的首 中 尾 三个数 取出来 进行比较取 中间那个数；

4：运算最快的代码组合之一

    三数取中 + 插排 

#include<stdio.h>void swap(int a, int b){int temp;temp = a;a = b;b = temp; }//插入排序 void Insertion_sort(int A[], int low, int high){int P,i; int N = high - low;for(P = 1; P < N; P++){int temp = A[P];for(i = P; i > 0 && A[i-1] >= temp; i--){A[i] = A[i-1];A[i-1] = temp; }} } //选取 一个基准 进行 分成两部分 //使用三数取中法选择枢轴 //int getstandard(int A[], int i, int j){ // // int mid = i + ((j - i) >> 1);//计算数组中间的元素的下标 // // //使用三数取中法选择枢轴 // if (A[mid] > A[j])//目标: arr[mid] <= arr[high] // { // swap(A[mid],A[j]); // } // if (A[i] > A[j])//目标: arr[low] <= arr[high] // { // swap(A[i],A[j]); // } // if (A[j] > A[i]) //目标: arr[low] >= arr[mid] // { // swap(A[mid],A[i]); // } // //此时，arr[mid] <= arr[low] <= arr[high] // int key = A[i]; // //low的位置上保存这三个位置中间的值 // //分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了 // // while(i < j){ // // while(i < j && A[j] >= key){ // j--; // } // if(i < j && A[j] < key){ // A[i] = A[j]; // } // // while(i < j && A[i] <= key){ // i++; // } // if(i < j && A[i] > key){ //前面的数如果大于key的话 就将前面的数放到后面? // A[j] = A[i]; // } // } // //出这个循环 // A[i] = key; // return i ; //}//此为选取第一个 数据作为基准 int getstandard(int A[], int left, int right){int i = left,j = right;int key = A[left];//选取 第一个数据为基准while(i < j){while(i < j && A[j] >= key){j--;} while(i < j && A[i] <= key){i++;}//当发现 从右边开始发现有比基准数小的时候，从左边开始 遇到比基准数大的时候//交换两个数 if(i < j){swap(A[i],A[j]);}} //出这个循环 交换基准数 和 i 与 j 相等时那个位置的数 A[left] = A[i];A[i] = key;return i; }void QuickSort(int A[] ,int low ,int high){if(low < high){int standard = getstandard(A, low, high);//递归两部分 QuickSort(A, low, standard-1);QuickSort(A, standard+1, high); }//当数据小于10的时候选择插入排序明显 比 快排速度更快 if(high - low < 10)Insertion_sort(A, low, high); } int main(){int i,n;scanf("%d",&n);int a[n];for(i=0; i<n; i++){scanf("%d",&a[i]);}QuickSort(a,0,n-1);for(i=0; i<n; i++){printf("%d ",a[i]);} }

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的数据结构 快速排序（详解）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。