c++快速排序詳解
快速排序,實際中最常用的一種排序算法,速度快,效率高,下面是小編分享的c++快速排序詳解,一起來看一下吧。
基本思想:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分所有數據要小,然後再按此方法對這兩部分數據分別進行快速排序。整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。
將數列變成上述形式,這一步很關鍵,做好這一步,才能對主元左右的部分進行遞歸調用。以下是實現這一部分的代碼:
int partition_sort(int arr[],int l,int r)//l是數組最左邊,r為最右邊
{
int j=l;//設計標記
int t=arr[l];//設置主元
for(int i=l+1;i<=r;i++)
{
if(arr[i]<t){
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
上述代碼中,我把最左邊的元素當作主元,這樣的代碼對大多數排序都很高效,但是不排除個別情況(當數組近乎有序或者當數組內有大量重複元素),這時,我們的.排序算法相比于歸並排序顯得並不是那麼高效,這和我們的排序算法原理密不可分,細細分析,當數組近乎有序時,我們的快速排序竟然退化到了O(n^2)級別,這顯然是非常不高效的。
要想實現上述不足的優化,我們可以將主元隨機選擇,或者採用其他方式的快速排序(雙路快速排序,三路快速排序),本篇內容僅作為學習快排的基本思想和基本實現,不深入涉及,有興趣的讀者可查閲資料瞭解。
下面是全部的實現代碼:
#include <iostream>
#include <math.h>
using namespace std;
//實現函數,用於partition的遞歸
int partition_sort(int arr[],int l,int r)//l是數組最左邊,r為最右邊
{
int j=l;//設計標記
int t=arr[l];//設置主元
for(int i=l+1;i<=r;i++)
{
if(arr[i]<t){
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
//實現遞歸的調用函數
void partition(int arr[],int l,int r)
{
if(l>=r)return ;
int p=partition_sort(arr,l,r);
partition(arr,l,p-1);
partition(arr,p+1,r);
}
int main()
{
int a[5];
for(int i=0;i<5;i++)
{
cin>>a[i];
}
partition(a,0,4);
for(int i=0;i<5;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
-
C語言如何提高程序效率
好的代碼沒有一個統一的衡量標準,在程序員們的世界裏大家也是各自按照自己的標準衡量着自己和別人的代碼。不過有一個標準幾乎是被所有人認同的。服役時間越長、出錯率越高的代碼就是好代碼。所有的編程方法、代碼技巧甚至於設計模式都是為了達到這個目的而產生...
-
C語言與JAVA的區別
很多人不明白C語言與C++和JAVE之間的區別,為此,為大家收集整理了下面的內容,歡迎閲讀!C語言C語言是一門通用計算機編程語言,應用廣泛。C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語...
-
C語言自增(++)和自減(--)
C語言源自KenThompson發明的B語言,那麼大家知道C語言自增(++)和自減(--)是什麼呢?下面一起來看看!一個整數自身加一可以這樣寫:a+=1;它等價於a=a+1;。但是在C語言中還有一種更簡單的寫法,就是a++;或者++a;。這種寫法叫做自加或自增;意思很明確,就是自身加一。相應...
-
C語言轉義字符和格式控制符參考
導語:字符型常量所表示的值是字符型變量所能包含的值。我們可以用ASCII表達式來表示一個字符型常量,或者用單引號內加反斜槓表示轉義字符。下面是C語言轉義字符和格式控制符參考,歡迎學習:轉義字符參考:a:蜂鳴,響鈴:回退:向後退一格f:換頁:換行,光標到下行行首:回車,光...