C語言簡單實現(xiàn)快速排序
更新時間：2019年01月17日 11:54:45 作者：n.xuanrui
快速排序是一種不穩(wěn)定排序，這篇文章主要為大家詳細(xì)介紹了C語言簡單實現(xiàn)快速排序，具有一定的參考價值，感興趣的小伙伴們可以參考一下
快速排序是一種不穩(wěn)定排序，它的時間復(fù)雜度為O(n·lgn)，最壞情況為O(n2)；空間復(fù)雜度為O(n·lgn)。
這種排序方式是對于冒泡排序的一種改進(jìn)，它采用分治模式，將一趟排序的數(shù)據(jù)分割成獨立的兩部分，其中一組數(shù)據(jù)的每個值都小于另一組。每一趟在進(jìn)行分類的同時實現(xiàn)排序。
其中每一趟的模式通過設(shè)置key當(dāng)基準(zhǔn)元素，key的選擇可以是數(shù)據(jù)的第一個，也可以是數(shù)據(jù)的最后一個。這里以每次選取數(shù)據(jù)的第一個為例：
具體代碼實現(xiàn)：
#include<stdio.h>
#define N 6
int fun(int arr[],int low,int high)
{
int key;
key=arr[low];
while(low<high)
{
while(low<high && arr[high]>=key)
high--;
if(low<high)
arr[low++]=arr[high];
while(low<high && arr[low]<=key)
low++;
if(low<high)
arr[high--]=arr[low];
}
arr[low]=key;
return low;
}
void quick_sort(int arr[],int start,int end)
{
int pos;
if(start<end)
{
pos=fun(arr,start,end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
}
int main()
{
int i;
int arr[N]={32,12,7,78,23,45};
for(i=0;i<N;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
quick_sort(arr,0,N-1);
for(i=0;i<N;i++)
{
printf("%d ",arr[i]);
}
return 0；
}
由于是第一次撰寫博客，許多地方?jīng)]有一個良好的習(xí)慣，還請讀者見諒。創(chuàng)建這個博客的目的實際上是為了讓自己對于數(shù)據(jù)結(jié)構(gòu)與算法加深印象，通過博客的形式展現(xiàn)出來一方面方便自己查閱，另一方面以希望能夠通過自己的微薄之力幫助到有需要的朋友。
也希望自己能夠堅持下去，認(rèn)真的去做這么一件事。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C++結(jié)構(gòu)體字節(jié)對齊和共用體大小
這篇文章主要介紹了C++結(jié)構(gòu)體字節(jié)對齊和共用體大小，結(jié)構(gòu)體內(nèi)存對齊在筆試和面試中經(jīng)常被問到，所以這篇文章做個總結(jié)，首先通過代碼驗證不同結(jié)構(gòu)體的內(nèi)存大小,需要的朋友可以參考下2021-11-11
這篇文章主要介紹了C++遍歷文件夾下文件的方法,實例分析了C++針對文件夾遍歷的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
現(xiàn)在正做一個接口，通過不同的連接字符串操作不同的數(shù)據(jù)庫。要用到mysql數(shù)據(jù)庫。通過網(wǎng)上的一些資料和自己的摸索，大致清楚了C++連接mysql的方法?？梢酝ㄟ^2種方法實現(xiàn)。第一種方法是利用ADO連接，第二種方法是利用mysql自己的api函數(shù)進(jìn)行連接。今天主要來講解下使用API2016-07-07
下面利用C語言來實現(xiàn)一個簡單的線程池，為了使得這個線程池庫使用起來更加方便，特在C實現(xiàn)中加入了一些OO的思想，與Objective-C不同，它僅僅是使用了struct來模擬了c++中的類，其實這種方式在linux內(nèi)核中大量可見2013-09-09
這篇文章主要為大家詳細(xì)介紹了C++繪制正弦曲線的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
invoke函數(shù)的實現(xiàn)原理是通過使用SFINAE（Substitution Failure Is Not An Error）技術(shù)來判斷可調(diào)用對象的類型,并根據(jù)類型調(diào)用對應(yīng)的調(diào)用方式,這篇文章主要介紹了C++ invoke與function的區(qū)別,需要的朋友可以參考下2023-10-10
這篇文章主要為大家詳細(xì)介紹了在QT環(huán)境中如何進(jìn)行CSV文件的初始化、寫入和讀取操作,本文為大家整理了相關(guān)的操作的多種方法,希望對大家有所幫助2025-04-04
今天小編就為大家分享一篇關(guān)于C++命名空間namespace的介紹與使用，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了C++中new運算符和delete運算符的使用,文章來自于微軟開發(fā)者文檔,因而根據(jù)Visual C++的一些特性來進(jìn)行講解,需要的朋友可以參考下2016-01-01
本文主要介紹了淺談QT內(nèi)存泄漏，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09