c++快速排序詳解
更新時間：2017年05月30日 23:45:37 作者：傻蝸牛
快速排序總體思想：先找到一個樞軸,讓他作為分水嶺,通過一趟排序將待排序的記錄分割成兩部分,前面一部分都比樞軸小,后面一部分樞軸大,然后又分別對這兩部分記錄繼續(xù)進行遞歸的排序,達到整個序列有序的目的
說一說快速排序
快速排序，實際中最常用的一種排序算法，速度快，效率高，在N*logN的同等級算法中效率名列前茅。·
基本思想：通過一趟排序將要排序的數(shù)據(jù)分割成兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分所有數(shù)據(jù)要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序。整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
將數(shù)列變成上述形式，這一步很關鍵，做好這一步，才能對主元左右的部分進行遞歸調用。以下是實現(xiàn)這一部分的代碼：
int partition_sort(int arr[],int l,int r)//l是數(shù)組最左邊，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;
}
上述代碼中，我把最左邊的元素當作主元，這樣的代碼對大多數(shù)排序都很高效，但是不排除個別情況（當數(shù)組近乎有序或者當數(shù)組內有大量重復元素），這時，我們的排序算法相比于歸并排序顯得并不是那么高效，這和我們的排序算法原理密不可分，細細分析，當數(shù)組近乎有序時，我們的快速排序竟然退化到了O（n^2)級別，這顯然是非常不高效的。
要想實現(xiàn)上述不足的優(yōu)化，我們可以將主元隨機選擇，或者采用其他方式的快速排序（雙路快速排序，三路快速排序），本篇內容僅作為學習快排的基本思想和基本實現(xiàn)，不深入涉及，有興趣的讀者可閱資料了解。
下面是全部的實現(xiàn)代碼：
#include <iostream>
#include <math.h>
using namespace std;
//實現(xiàn)函數(shù)，用于partition的遞歸
int partition_sort(int arr[],int l,int r)//l是數(shù)組最左邊，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;
}
//實現(xiàn)遞歸的調用函數(shù)
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;
}
相關文章
紅黑樹(Red?Black?Tre)是一種自平衡二叉查找樹,是在計算機科學中用到的一種數(shù)據(jù)結構,典型的用途是實現(xiàn)關聯(lián)數(shù)組,下面這篇文章主要給大家介紹了關于C++使用一棵紅黑樹同時封裝出map和set的相關資料,需要的朋友可以參考下2023-04-04
程序在運行過程中，有對也就有錯，正確那么就不用說了，但是如果錯誤，那么我們如何快速的定位到錯誤的位置，以及知道發(fā)生了什么錯誤。當一個函數(shù)發(fā)現(xiàn)自己無法處理的異常，就會拋出一個異常，讓函數(shù)調用者直接或者間接的處理這個錯誤。本文將詳解介紹c++中的異常2021-06-06
本文主要介紹了C++中Copy-Swap實現(xiàn)拷貝交換，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07
這篇文章主要為大家介紹了C語言題解Leetcode56合并區(qū)間實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
這篇文章主要給大家介紹了關于C語言中sizeof函數(shù)的基本使用的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2018-03-03
這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)將YUV文件轉為JPEG格式,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2023-12-12
字符串中找出連續(xù)最長的數(shù)字字符串的實例代碼
這篇文章介紹了字符串中找出連續(xù)最長的數(shù)字字符串的實例代碼，有需要的朋友可以參考一下2013-09-09
這篇文章介紹了boost.asio框架系列之socket編程，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
std::list是支持常數(shù)時間從容器任何位置插入和移除元素的容器,下面這篇文章主要給大家介紹了關于C++?STL標準庫之std::list使用介紹及用法詳解的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-11-11
Qt中提供了強大的2D繪圖系統(tǒng),可以使用同一API實現(xiàn)在屏幕和繪圖設備上進行繪制，本文就詳細的介紹了Qt繪制坐標圖、柱狀圖、折線圖、餅圖、曲線圖、散點圖等，感興趣的可以了解一下2021-05-05