快速排序

快速排序是一種基于分治的算法，其基本思想是將一個大數組按照一個【基準數】分為左右兩份，左邊的部分都不大于基準數，右邊的部分都不小于基準數。然后，對這兩份在分別應用快速排序，直到剩下一個元素為止。快速排序的平均時間復雜度為nlog(n)。

下面是選取數組最左邊的元素為基準元素的快排算法：

//應該隨機選擇一個數為主元，這里選擇最右邊的一個數為主元 ## 快速排序 int partition(int a[],int left,int right){int temp=a[left];//選擇數組最左邊的元素為基準while(left<right){while(left<right&&a[right]>temp) right--;a[left]=a[right];while(left<right&&a[left]<=temp) left++;a[right]=a[left];}a[left]=temp;return left; } //法二 int partition(int a[],int left,int right){ int small=left-1;//記錄比主元小的數 for(int i=left;i<right;i++){if(a[i]<a[right]){++small;if(small!=i){swap(a[i],a[small]);}}}small++;swap(a[small],a[right]);return small; }void quickSort(int a[],int left,int right){if(left<right){int pos=partion(a,left,right);quickSort(a,left,pos-1);quickSort(a,pos+1,right);} }

快速排序算法當序列中元素的排列比較隨機時效率最高，但是當序列中元素接近有序時，會達到最壞的時間復雜度O(n2)，產生這種情況的主要原因在于沒有把當前區間劃分為兩個長度接近的子區間。
解決辦法就是隨機選取基準元素，也就是對A[left,...,right]來說，不總是用A[left]作為基準元素，而是從A[left],A[left+1].....,A[right]中隨機選擇一個作為基準元素。
這樣對于任意輸入數據的期望時間復雜度就能達到O(nlogn)。
另外快速排序是不穩定的。

基于快排的partion函數，還有一道比較常見的面試題就是【求最小/大的k個數】，下面是求最小的k個數。

int partion(vector<int> &input,int left,int right){int temp=input[left];while(left<right){while(left<right&&input[right]>temp){right--;}input[left]=input[right];while(left<right&&input[left]<=temp){left++;}input[right]=input[left];}input[left]=temp;return left; } vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {int start=0;int end=input.size()-1;int index=partion(input,start,end); // printf("hello %d\n",index);while(index!=k-1){if(index>k-1){end=index-1;index=partion(input,start,end);}else{start=index+1;index=partion(input,start,end);}}vector<int> rnt;for(int i=0;i<k;i++){printf("%d ",input[i]);rnt.push_back(input[i]);}return rnt; }

堆排序

堆排序是使用堆這種數據結構來實現的，首先用一個數組實現堆，主要的步驟是向下調整的過程，如下：

#include<cstdio> #include<algorithm> using namespace std;const int maxn=10010; int heap[maxn]={-1,9,8,1,2,6,7,4,3,5,0},n=10;void downAdjust(int low,int high){int i=low,j=i*2;while(j<=high){if(j+1<=high&&heap[j+1]>heap[j]){j++;}if(heap[j]>heap[i]){swap(heap[j],heap[i]);i=j;j=i*2;}else{break;}}} void createHeap(){for(int i=n/2;i>=1;i--){downAdjust(i,n);} } void heapSort(){createHeap();for(int i=n;i>1;i--){swap(heap[i],heap[1]);downAdjust(1,i-1);} } int main(){heapSort();for(int i=1;i<=n;i++){printf("%d ",heap[i]);} return 0;}

歸并排序

void merge(int a[],int L1,int R1,int L2,int R2){int i=L1,j=L2;int temp[maxn],index=0;while(i<=R1&&j<=R2){if(a[i]<a[j]){temp[index++]=a[i++];}else{temp[index++]=a[j++];}}while(i<=R1) temp[index++]=a[i++];while(j<=R2) temp[index++]=a[j++];for(i=0;i<index;i++){a[L1+1]=temp[i];} } // 遞歸實現 void mergeSort(int a[],int left,int right){if(left<right){int mid=(left+right)/2;mergeSort(a,left,mid);mergeSort(a,mid+1,rigt);mergeSort(a,left,mid,mid+1,right);} }// 非遞歸實現 void mergeSort(int a[]){for(int step=2;step/2<n;stem*=2){for(int i0;i<n;i+=step){int mid=i+step/2-1if(mid+1<n){merge(a,i,mid,mid+1,min(i+stemp-1,n-1));}}} }

轉載于:https://www.cnblogs.com/sqmax/p/10199279.html

總結

以上是生活随笔為你收集整理的几种排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。