/*
創(chuàng)新互聯(lián)建站是一家專注于網(wǎng)站建設(shè)、做網(wǎng)站與策劃設(shè)計(jì),東寧網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:東寧等地區(qū)。東寧做網(wǎng)站價(jià)格咨詢:18982081108
//@author?Program_Yuan
//時(shí)間:2014年6月19日21:19:23
*/
/*
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)作業(yè)
實(shí)驗(yàn)4:排序1
要求:
1、直接插入排序;
2、折半插入排序;
3、希爾排序;
4、冒泡排序
5、簡(jiǎn)單選擇排序
6、樹型選擇排序
7、堆排序
交作業(yè)時(shí)間:7月2日
*/
//各種排序
//以下排序均已升序?yàn)闃?biāo)準(zhǔn)
//測(cè)試數(shù)據(jù)??a[]?=?{32,21,10,100,43,54,12,78,10,3223,34,31,54,76,2,6,2,4};
#include?iostream
#include?cstring
using?namespace?std;
void?bubble_sort(int?a[],int?n);
void?quick_sort(int?a[],int?n);
void?simple_select_sort(int?a[],int?n);
void?direct_insert_sort(int?a[],int?n);
void?middle_insert_sort(int?a[],int?n);
void?shell_sort(int?a[],int?n);
void?heap_sort(int?a[],int?n);
void?change_heap(int?a[],int?i,int?n);
inline?void?swap(int?a,int?b);
int?main()
{
int?a[]?=?{32,21,10,100,43,54,12,78,10,3223,34,31,54,76,2,6,2,4};
int?n?=?sizeof(a)?/?sizeof(int);
//bubble_sort(a,n);//冒泡測(cè)試
//quick_sort(a,n);//快排測(cè)試
//simple_select_sort(a,n);//簡(jiǎn)單選擇排序
//direct_insert_sort(a,n);//直接插入排序
//middle_insert_sort(a,n);//折半插入排序
//shell_sort(a,n);//希爾排序
heap_sort(a,n);//堆排序
for?(int?i?=?0;?i??n;?i++)
{
couta[i]"??";
}
coutendl;
return?0;
}
void?bubble_sort(int?a[],int?n)//冒泡排序
{
for?(int?i?=?0;?i??n;?i++)
{
for?(int?j?=?i?+?1;?j??n;?j++)
{
if?(a[i]??a[j])
{
int?t?=?a[i];
a[i]?=?a[j];
a[j]?=?t;
}
}
}
}//冒泡排序
void?quick_sort(int?a[],int?n)//快排
{
int?key?=?a[0];//key為支點(diǎn),即樞軸
int?low,high;
low?=?0;
high?=?n?-?1;//low,high分別為兩端點(diǎn)值
if?(n??1)
{
while?(low??high)
{
for?(;?high??low;?high--)
{
if?(a[high]??key)
{
a[low]?=?a[high];
break;
}
}
for?(;?low??high;?low++)
{
if?(a[low]??key)
{
a[high]?=?a[low];
break;
}
}
}
}
else
{
return;
}
a[low]?=?key;
quick_sort(a,low);
quick_sort(a?+?low?+?1,?n?-?low?-?1);
}//快速排序
void?simple_select_sort(int?a[],int?n)//簡(jiǎn)單選擇排序
{
int?min?=?0;
for?(int?i?=?0;?i??n;?i++)
{
for?(int?j?=?i;?j??n;?j++)
{
if?(a[min]??a[j])
{
min?=?j;
}
}
int?t?=?a[i];
a[i]?=?a[min];
a[min]?=?t;
min?=?i?+?1;
}
}//簡(jiǎn)單選擇排序
void?direct_insert_sort(int?a[],int?n)//插入排序----直接插入排序
{
int?j;//控制循環(huán)
for?(int?i?=?1;?i??n;?i++)
{
if?(a[i]??a[i?-?1])
{
int?key?=?a[i];
for?(j?=?i?-?1;?key??a[j]??j?=?0;?j--)
{
a[j?+?1]?=?a[j];
}
a[j?+?1]?=?key;
}
}
}//插入排序----直接插入排序
void?middle_insert_sort(int?a[],int?n)//折半插入排序
{
int?t?=?0;
for?(int?g?=?1;?g??n;?g++)
{
if?(a[t]??a[g])
{
t?=?g;
}
}
int?k?=?a[t];
a[t]?=?a[0];
a[0]?=?k;
for(int?i?=?2;?i??n;?i++)
{
int?low?=?1;
int?hight?=?i?-?1;
int?key?=?a[i];
int?j;//控制循環(huán)
while?(low?=?hight)
{
int?mid?=?(low?+?hight)?/?2;
if?(a[mid]??key)
{
hight?=?mid?-?1;
}
else?if?(a[mid]??key)
{
low?=?mid?+?1;
}
else
{
break;
}//if
}//for
for?(j?=?i?-?1;?j?=?hight?+?1;?j--)
{
a[j?+?1]?=?a[j];
}//for
a[j?+?1]?=?key;
}//while
}//函數(shù)
void?shell_sort(int?a[],int?n)//希爾排序
{
int?interval?=??n?/?2;??//interval是間隔??即增量
int?g;
while?(interval??0)
{
for?(int?j?=?interval;?j??n;?j++)
{
int?key?=?a[j];
for?(g?=?j?-?interval;?g?=?0??key??a[g];?g?-=?interval)
{
a[g?+?interval]?=?a[g];
}//移動(dòng)到插入的地方
a[g?+?interval]?=?key;
}//n趟排序
interval?/=?2;
}//while
}//希爾排序
void?swap(int?a,int?b)//堆排序的輔助函數(shù)----交換兩個(gè)數(shù)(為了提高效率,使用內(nèi)聯(lián)函數(shù))
{
int?t?=?a;
a?=?b;
b?=?t;
}
void?change_heap(int?a[],int?i,int?n)//調(diào)整堆
{
int?n_child;
for?(?;?2?*?i?+?1??n;?i?=?n_child)
{
n_child?=?2?*?i?+?1;
if?(n_child??n?-?1??a[n_child?+?1]??a[n_child])
n_child++;
if?(a[n_child]??a[i])
{
swap(a[n_child],a[i]);
}
else
{
break;
}
}
}//堆排序----調(diào)整堆
void?heap_sort(int?a[],int?n)//建立堆
{
//調(diào)整從第一個(gè)非葉子結(jié)點(diǎn)開始
for?(int?i?=?n?/?2?-?1;?i?=?0;?i--)
{
change_heap(a,i,n);
}
for(int?j?=?n?-?1;?j??0;?j--)
{
swap(a[j],a[0]);
change_heap(a,0,j);
}
}//堆排序----輸出最大
/*
//幫助文檔?-_-||
//作業(yè)第四個(gè)
//一個(gè)最簡(jiǎn)單的冒泡排序???注釋:冒泡排序是穩(wěn)定的排序算法,復(fù)雜度為?n*n
void?bubble_sort(int?a[],int?n);
//快速排序???注釋:快排是對(duì)冒泡排序的改進(jìn),不是穩(wěn)定排序,復(fù)雜度為log(n)
//效率很高?編碼復(fù)雜?思想:首先找一個(gè)支點(diǎn)(樞軸,通常選取第一個(gè)元素),
//第一遍把大于支點(diǎn)的元素放在右邊,小于支點(diǎn)的元素放在左邊
//第二遍也是這樣的思想?把左右同時(shí)看做是一個(gè)有待排序的數(shù)列?利用遞歸的思想
void?quick_sort(int?a[],int?n);
//作業(yè)第五個(gè)
//選擇排序----簡(jiǎn)單選擇排序?注釋:復(fù)雜度?n*n??不是穩(wěn)定排序
void?simple_select_sort(int?a[],int?n);
//作業(yè)第一個(gè)
//插入排序----直接插入排序?注釋:??復(fù)雜度?n*n??穩(wěn)定的排序算法
void?direct_insert_sort(int?a[],int?n);
//作業(yè)第二個(gè)
//折半插入排序???注釋:????復(fù)雜度??n*n
void?middle_insert_sort(int?a[],int?n);
//作業(yè)第三個(gè)
//希爾排序???????注釋:????不穩(wěn)定
void?shell_sort(int?a[],int?n);
//作業(yè)第七個(gè)
//堆排序?????????注釋:????不穩(wěn)定
void?heap_sort(int?a[],int?n);//建立堆
void?change_heap(int?a[],int?i,int?n);//調(diào)整堆
inline?void?swap(int?a,int?b);//堆排序的輔助函數(shù)?用來交換兩個(gè)數(shù)據(jù)的值
//我是大好人
*/
#includestdio.h
void?sort(float?*a,?int?n)
{
int?i,j,tmp;
for(i=0;?in-1;?i++)
for(j=0;?jn-i-1;?j++)
if(a[j]a[j+1])
{
tmp?=?a[j];
a[j]?=?a[j+1];
a[j+1]?=?tmp;
}
}
void?main()
{
float?a[5];
int?i;
printf("請(qǐng)輸入五個(gè)數(shù)(逗號(hào)隔開):");
scanf("%f,%f,%f,%f,%f",a[0],a[1],a[2],a[3],a[4]);
sort(a,5);
printf("排序后為:");
for(i=0;?i5;?i++)
printf("%.2f?",a[i]);
printf("\n");
}
或者三個(gè)數(shù)的。
void sort(int *a, int *b, int *c)
{
int tmp;
if(*a*b){
tmp = *b;
*b = *a;
*a = tmp;
}
if(*a*c){
tmp = *c;
*c = *a;
*a = tmp;
}
if(*b*c){
tmp = *c;
*c = *b;
*b = tmp;
}
return;
}
擴(kuò)展資料:
C語言中沒有預(yù)置的sort函數(shù)。如果在C語言中,遇到有調(diào)用sort函數(shù),就是自定義的一個(gè)函數(shù),功能一般用于排序。
一、可以編寫自己的sort函數(shù)。
如下函數(shù)為將整型數(shù)組從小到大排序。void sort(int *a, int l)//a為數(shù)組地址,l為數(shù)組長(zhǎng)度。
{ ?
int i, j; ?
int v; ? ?//排序主體
for(i = 0; i l - 1; i ++) ? ? ?
for(j = i+1; j l; j ++)
?
{ ? ? ? ? ?
if(a[i] a[j])//如前面的比后面的大,則交換。
? ? ?
{
? ? ? ? ?
v = a[i];
? ? ? ? ?
a[i] = a[j];
? ? ? ? ?
a[j] = v;
? ? ?
}
?
}
}
對(duì)于這樣的自定義sort函數(shù),可以按照定義的規(guī)范來調(diào)用。
二、C語言有自有的qsort函數(shù)。
功 能: 使用快速排序例程進(jìn)行排序。頭文件:stdlib.h
原型:
void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
參數(shù):
1、待排序數(shù)組首地址。
2、數(shù)組中待排序元素?cái)?shù)量。
3、各元素的占用空間大小4 指向函數(shù)的指針,用于確定排序的順序,這個(gè)函數(shù)必須要自己寫比較函數(shù),即使要排序的元素是int,float一類的C語言基礎(chǔ)類型。
include cstdlib 或 #include stdlib.h
qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))
參數(shù)表
*base: 待排序的元素(數(shù)組,下標(biāo)0起)。
num: 元素的數(shù)量。
width: 每個(gè)元素的內(nèi)存空間大小(以字節(jié)為單位)??捎胹izeof()測(cè)得。
int(*)compare: 指向一個(gè)比較函數(shù)。*elem1 *elem2: 指向待比較的數(shù)據(jù)。
比較函數(shù)的返回值
返回值是int類型,確定elem1與elem2的相對(duì)位置。
elem1在elem2右側(cè)返回正數(shù),elem1在elem2左側(cè)返回負(fù)數(shù)。
控制返回值可以確定升序/降序。
產(chǎn)生隨機(jī)數(shù)的函數(shù)也是rand(),不是rank().
1、冒泡排序(最常用)
冒泡排序是最簡(jiǎn)單的排序方法:原理是:從左到右,相鄰元素進(jìn)行比較。每次比較一輪,就會(huì)找到序列中最大的一個(gè)或最小的一個(gè)。這個(gè)數(shù)就會(huì)從序列的最右邊冒出來。(注意每一輪都是從a[0]開始比較的)
以從小到大排序?yàn)槔?,第一輪比較后,所有數(shù)中最大的那個(gè)數(shù)就會(huì)浮到最右邊;第二輪比較后,所有數(shù)中第二大的那個(gè)數(shù)就會(huì)浮到倒數(shù)第二個(gè)位置……就這樣一輪一輪地比較,最后實(shí)現(xiàn)從小到大排序。
2、雞尾酒排序
雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時(shí)排序, 是冒泡排序的一種變形。該算法與冒泡排序的不同處在于排序時(shí)是以雙向在序列中進(jìn)行排序。
原理:數(shù)組中的數(shù)字本是無規(guī)律的排放,先找到最小的數(shù)字,把他放到第一位,然后找到最大的數(shù)字放到最后一位。然后再找到第二小的數(shù)字放到第二位,再找到第二大的數(shù)字放到倒數(shù)第二位。以此類推,直到完成排序。
3、選擇排序
思路是設(shè)有10個(gè)元素a[1]-a[10],將a[1]與a[2]-a[10]比較,若a[1]比a[2]-a[10]都小,則不進(jìn)行交換。若a[2]-a[10]中有一個(gè)以上比a[1]小,則將其中最大的一個(gè)與a[1]交換,此時(shí)a[1]就存放了10個(gè)數(shù)中最小的一個(gè)。同理,第二輪拿a[2]與a[3]-a[10]比較,a[2]存放a[2]-a[10]中最小的數(shù),以此類推。
4、插入排序
插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上,一次插入一個(gè)元素*
一般來說,插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。
具體算法描述如下:
⒈ 從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序
⒉ 取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描
⒊ 如果該元素(已排序)大于新元素,將該元素移到下一位置
⒋ 重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復(fù)步驟2~5
首先這是一種快速排序的算法,你也應(yīng)該知道,快速排序就是選擇序列中的一個(gè)元素作為基準(zhǔn),通過循環(huán)找到這個(gè)基準(zhǔn)最終的位置,并把所有小于這個(gè)基準(zhǔn)的元素移到這個(gè)位置的左邊,大于基本的元素移到右邊,這樣再對(duì)這個(gè)基準(zhǔn)的左右兩邊分別遞歸調(diào)用自己,最終就能得到排序的結(jié)果。
再來解釋一下這個(gè)例子,它選擇的基準(zhǔn)就是v[(left+right)/2],然后將這個(gè)基準(zhǔn)雨v[left]交換,現(xiàn)在假設(shè)你想從頭排序到最后,則你會(huì)將left傳個(gè)0,也就是他將這個(gè)基準(zhǔn)和V[0]交換了,這個(gè)時(shí)候開始循環(huán),因?yàn)榈谝粋€(gè)元素是基準(zhǔn),所以從第二個(gè)元素開始循環(huán)(也就是left+1),然后到if判斷部分,如果v[i]v[left],也就是說這個(gè)時(shí)候已經(jīng)至少有一個(gè)元素比基準(zhǔn)小了,所以基準(zhǔn)至少在v[1]或者之后了,所以他把你找到的這個(gè)比基準(zhǔn)小的v[i]和v[++last]交換,這時(shí)候v[i]的位置已經(jīng)是在基準(zhǔn)的正確位置或者之前了,不會(huì)在基準(zhǔn)之后的,所以這就實(shí)現(xiàn)了把比基準(zhǔn)小的元素移到基準(zhǔn)的正確位置之前,你說的【第一遍執(zhí)行過程中,第8行l(wèi)ast=left=0,那么到了11行時(shí)相當(dāng)于交換v[1]和v[0+1]】這沒有錯(cuò),確實(shí)是在自己交換自己,但是這樣并不違背前面的思路不是么?當(dāng)if條件不滿足的時(shí)候,last是不會(huì)增加的,但是i會(huì)一直加1,所以last和i就會(huì)不同,這只是在將比基準(zhǔn)小的元素移到基準(zhǔn)之前,每有一個(gè)比基準(zhǔn)小的,last就加1,這樣當(dāng)你循環(huán)一遍之后的last值就是基準(zhǔn)應(yīng)該在的位置,而且這個(gè)時(shí)候,所有比基本小的元素也都在last之前了,這時(shí)候last位置的元素也是比基準(zhǔn)小的,這沒關(guān)系,因?yàn)橹筮€有一句swap[v,last,left],到目前位置,基準(zhǔn)的位置找到了,基準(zhǔn)左邊的元素都比基準(zhǔn)小,右邊都比基準(zhǔn)大,再對(duì)基準(zhǔn)的左右兩邊遞歸調(diào)用自己,就完成了序列的排序。
1、sort()函數(shù)描述:對(duì)給定區(qū)間所有元素進(jìn)行排序。
sort()函數(shù)語法:sort(begin,end),表示一個(gè)范圍。
2、sort()函數(shù)舉例:
#include?algorithm
#include?iostream
using?namespace?std;
main()
{
int?a[11]={2,4,8,5,7,1,10,6,9,3};//a的長(zhǎng)度=待排數(shù)據(jù)個(gè)數(shù)+1
sort(a,a+10);//對(duì)[a,a+10)排序
for(int?i=0;i10;++i)?couta[i]endl;
}