//聯(lián)系人:石虎QQ: 1224614774昵稱:嗡嘛呢叭咪哄
//常用的排序算法
細(xì)節(jié)請看:http://blog.csdn.net/shihuboke/article/details/77430132
#include
usingnamespacestd;
typedefintElemType;
一、插入排序
/*
1骗炉、插入排序
（1）直接插入排序算法
算法思想：將等排序列劃分為有序與無序兩部分撬腾，然后再依次將無序部分插入到已經(jīng)有序的部分柏副，最后
就可以形成有序序列。
操作步驟如下：
1）查找出元素L（i）在表中的插入位置K部默；
2）將表中的第K個(gè)元素之前的元素依次后移一個(gè)位置甫匹；
3）將L（i）復(fù)制到L（K）。
時(shí)間復(fù)雜度為：O(n^2)
*/
voidInsertSort(ElemTypearr[],intlength)
{
inti, j;
ElemTypeguard;//哨兵
for(i =1; i < length; ++i)
{
if(arr[i] < arr[i-1])//在無序部分尋找一個(gè)元素撇贺，使之插入到有序部分后仍然有序
{
guard = arr[i];//復(fù)制到“哨兵”
//將第i個(gè)元素之前的元素依次后移一個(gè)位置
for(j = i -1; arr[j] > guard; j--)
{
arr[j +1] = arr[j];
}
arr[j +1] = guard;//復(fù)制到插入位置
}
}
}
二、折半插入排序
/*
2造成、折半插入排序
使用于排序表為順序存儲(chǔ)的線性表
在查找插入位置時(shí)显熏，采用折半查找
算法思想是：
1）設(shè)置折半查找范圍雄嚣；
2）折半查找
3）移動(dòng)元素
4）插入元素
5）繼續(xù)操作1）晒屎、2）喘蟆、3）、4）步鼓鲁，直到表成有序蕴轨。
*/
voidBinaryInsertSort(ElemTypearr[],intlength)
{
inti, j, low, high, mid;
ElemTypetmp;
for( i =1; i < length; ++i )
{
tmp = arr[i];//復(fù)制到哨兵
//設(shè)置折半查找范圍
low =0;
high = i;
while(low <= high)//折半查找
{
mid = (low + high) /2;
if(arr[mid] > tmp)//在左半部分查找
{
high = mid -1;
}
else
{
low = mid +1;//在右半部分查找
}
}
//移動(dòng)元素
for( j = i -1; j >= high +1; --j )
{
arr[j +1] = arr[j];
}
arr[j +1] = tmp;
}
}
三、希爾(Shell)排序
/*
3骇吭、希爾(Shell)排序
基本思想：
先將待排序的表分割成若干個(gè)形若L[i, i+d, i+2d, ..., i+kd]的“特殊”子表橙弱，分別進(jìn)行直接插入排序，
當(dāng)整個(gè)表已呈“基本有序”時(shí)燥狰，再對全體記錄進(jìn)行一次直接插入排序棘脐。
算法過程：
1）先取一個(gè)小于n的步長d1,把表中全部記錄分成d1個(gè)組，所有距離為d1的倍數(shù)的記錄放在同一組中龙致，在各
組中進(jìn)行直接插入排序蛀缝；
2）然后取第二個(gè)步長d2 < d1,重復(fù)步驟1
3）直到dk = 1，再進(jìn)行最后一次直接插入排序
*/
voidShellSort(ElemTypearr[],intlength)
{
inti, j, dk = length /2;
ElemTypetmp;
while(dk >=1)//控制步長
{
for(i = dk; i < length; ++i)
{
if(arr[i] < arr[i - dk])
{
tmp = arr[i];//暫存
//后移
for(j = i - dk; j >=0&& tmp < arr[j]; j -= dk)
{
arr[j + dk] = arr[j];
}
arr[j + dk] = tmp;
}
}
dk /=2;
}
}
四目代、冒泡排序算法
/*
4屈梁、冒泡排序算法
基本思想：
假設(shè)待排序的表長為n，從后向前或從前向后兩兩比較相鄰元素的值榛了，若為逆序在讶，則交換之，直到序列比較完霜大。
這樣一回就稱為一趟冒泡构哺。這樣值較大的元素往下“沉”，而值較小的元素入上“浮”战坤。
時(shí)間復(fù)雜度為O(n^2)
*/
voidBubbleSort(ElemTypearr[],intlength)
{
inti, j;
ElemTypetmp;
for(i =0; i < length -1; ++i)//趟次
{
for(j = i +1; j < length; ++j)
{
if(arr[i] > arr[j])
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
五遮婶、快速排序算法
/*
5、快速排序算法
基本思想：基于分治法湖笨，在待排序的n個(gè)元素中任取一個(gè)元素pivot作為基準(zhǔn)旗扑，通過一趟排序?qū)⒋判虮韯澐譃楠?dú)立的
兩部分L[1..k-1]和L[k+1 .. n],使得第一部分中的所有元素值都小于pivot，而第二部分中的所有元素值都大于pivot慈省，
則基準(zhǔn)元素放在了其最終位置L（K）上臀防，這個(gè)過程為一趟快速排序。而后分別遞歸地對兩個(gè)子表重復(fù)上述過程边败，直到每
部分內(nèi)只有一個(gè)元素或?yàn)榭諡橹垢ぶ裕此性囟挤旁诹似渥罱K位置上。
*/
intPartition(ElemTypearr[],intleft,intright)
{
ElemTypepivot = arr[left];//以當(dāng)前表中第一個(gè)元素為樞軸值
while(left < right)
{
//從右向左找一個(gè)比樞軸值小的元素的位置
while(left < right && arr[right] >= pivot)
{
--right;
}
arr[left] = arr[right];//將比樞軸值小的元素移動(dòng)到左端
//從左向右查找比樞軸值大的元素的位置
while(left < right && arr[left] <= pivot)
{
++left;
}
arr[right] = arr[left];//將比樞軸值大的元素移動(dòng)到右端
}
arr[left] = pivot;//將樞軸元素放在最終位置
returnleft;
}
voidQuickSort(ElemTypearr[],intleft,intright)
{
if(left < right)
{
intpivotPos =Partition(arr, left, right);//劃分
QuickSort(arr, left, pivotPos -1);//快速排序左半部分
QuickSort(arr, pivotPos +1, right);//快速排序右半部分
}
}
六笑窜、簡單選擇排序算法
/*
6致燥、簡單選擇排序算法
基本思想：
假設(shè)排序表為L[1...n],第i趟排序從表中選擇關(guān)鍵字最小的元素與Li交換，第一趟排序可以確定一個(gè)元素的
最終位置排截，這樣經(jīng)過n-1趟排序就可以使得整個(gè)排序表有序嫌蚤。
*/
voidSelectSort(ElemTypearr[],intlength)
{
inti, j, min;
ElemTypetmp;
for(i =0; i < length -1; ++i)//需要n-1趟
{
min = i;
for(j = i +1; j < length; ++j)
{
if(arr[j] < arr[min])//每一趟選擇元素值最小的下標(biāo)
{
min = j;
}
}
if(min != i)//如果第i趟的Li元素值該趟找到的最小元素值辐益，則交換，以使Li值最小
{
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}
七脱吱、堆排序算法
/*
7智政、堆排序算法
堆的定義如下：n個(gè)關(guān)鍵字序列號(hào)L[1..n]稱為堆，僅當(dāng)該序列滿足：
1）L(i) <= L(2i)且L(i) <= L(2i+1)或2)L(i) >= L(2i)且L(i) >= L(2i+1)
滿足第一種情況的堆箱蝠，稱為小根堆（小頂堆）续捂；
滿足第二種情況的堆，稱為大根堆（大頂堆）宦搬。
*/
voidHeapAdjust(ElemType*a,inti,intsize)//調(diào)整堆
{
intlchild =2* i;//i的左孩子節(jié)點(diǎn)序號(hào)
intrchild =2* i +1;//i的右孩子節(jié)點(diǎn)序號(hào)
intmax = i;//臨時(shí)變量
if(i <= size /2)//如果i是葉節(jié)點(diǎn)就不用進(jìn)行調(diào)整
{
if(lchild <= size && a[lchild] > a[max])
{
max = lchild;//左孩子比雙親值還大牙瓢，需要調(diào)整
}
if(rchild <= size && a[rchild] > a[max])
{
max = rchild;//右孩子比雙親值還大，需要調(diào)整
}
if(max != i)//需要調(diào)整
{
ElemTypetmp = a[max];
a[max] = a[i];
a[i] = tmp;
HeapAdjust(a, max, size);//避免調(diào)整之后以max為父節(jié)點(diǎn)的子樹不是堆
}
}
}
voidBuildHeap(ElemType*a,intsize)//建立堆
{
for(inti = size /2; i >=0; i--)//非葉節(jié)點(diǎn)最大序號(hào)值為size/2
{
HeapAdjust(a, i, size);
}
}
voidHeapSort(ElemType*a,intsize)//堆排序
{
BuildHeap(a,size);
for(inti = size -1; i >=0; i--)
{
swap(a[0], a[i]);//交換堆頂和最后一個(gè)元素间校，即每次將剩余元素中的最大者放到最后面
BuildHeap(a, i-1);//將余下元素重新建立為大頂堆
HeapAdjust(a,1,i-1);//重新調(diào)整堆頂節(jié)點(diǎn)成為大頂堆
}
}
voidDisplay(ElemType arr[],intlength)
{
for(inti =0; i < length; ++i )
{
cout << arr[i] <<" ";
}
cout << endl;
}
intmain()
{
ElemType arr[] = {2,1,5,3,4,0,6,9, -1,4,12};
HeapSort(arr,sizeof(arr) /sizeof(ElemType));
Display(arr,sizeof(arr) /sizeof(ElemType));
return0;
}
謝謝!!!
