c說話完成冒泡排序、希爾排序等多種算法示例。本站提示廣大學習愛好者：（c說話完成冒泡排序、希爾排序等多種算法示例）文章只能為提供參考，不一定能成為您想要的結果。以下是c說話完成冒泡排序、希爾排序等多種算法示例正文
完成以下排序
拔出排序O(n^2)
冒泡排序 O(n^2)
選擇排序 O(n^2)
疾速排序 O(n log n)
堆排序 O(n log n)
合並排序 O(n log n)
希爾排序 O(n^1.25)
1.拔出排序 O(n^2)
普通來講，拔出排序都采取in-place在數組上完成。詳細算法描寫以下：
⒈ 從第一個元素開端，該元素可以以為曾經被排序
⒉ 掏出下一個元素，在曾經排序的元素序列中從後向前掃描
⒊ 假如該元素（已排序）年夜於新元素，將該元素移到下一名置
⒋ 反復步調3，直到找到已排序的元素小於或許等於新元素的地位
⒌ 將新元素拔出到下一名置中
⒍ 反復步調2~5
假如比擬操作的價值比交流操作年夜的話，可以采取二分查找法來削減比擬操作的數量。該算法可以以為是拔出排序的一個變種，稱為二分查找排序。
void insert_sort(int* array,unsignedint n){
int i,j;
int temp;
for(i=1;i<n;i++){
temp=*(array+i);
for(j=i;j>0&&*(array+j-1)>temp;j--){
*(array+j)=*(array+j-1);
}
*(array+j)=temp;
}
}
2.冒泡排序 O(n^2)
冒泡排序算法的運作以下：
比擬相鄰的元素。假如第一個比第二個年夜，就交流他們兩個。
對每對相鄰元素作異樣的任務，從開端第一對到開頭的最初一對。在這一點，最初的元素應當會是最年夜的數。
針對一切的元素反復以上的步調，除最初一個。
連續每次對愈來愈少的元素反復下面的步調，直到沒有任何一對數字須要比擬。
#include<stdio.h>
#defineSIZE8
void bublle_sort(int a[],int n){//n為數組a的元素個數
int i,j,temp;
for(j=0;j<n-1;j++)
for(i=0;i<n-1-j;i++)
if(a[i]>a[i+1]){//數組元素年夜小按升序分列
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
int main(){
int number[SIZE]={95,45,15,78,84,51,24,12};
int i;
bublle_sort(number,SIZE);
for(i=0;i<SIZE;i++){
printf("%d",number[i]);
}
printf("\n");
}
3.選擇排序 O(n^2)
void select_sort(int * a, int n){
register int i, j, min, t;
for( i =0; i < n -1; i ++) {
min = i; //查找最小值
for( j = i +1; j < n; j ++)
if( a[min] > a[j])
min = j; //交流
if(min != i) {
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
4.疾速排序 O(n log n)
void QuickSort(int a[],int numsize){//a是整形數組，numsize是元素個數
int i=0,j=numsize-1;
int val=a[0];//指定參考值val年夜小
if(numsize>1){//確保數組長度至多為2，不然無需排序
while(i<j{//輪回停止前提
for(;j>i;j--)//從後向前搜刮比val小的元素，找到後填到a[i]中並跳出輪回
if(a[j]<val){
a[i]=a[j];break;
}
for(;i<j;i++)//早年往後搜刮比val年夜的元素，找到後填到a[j]中並跳出輪回
if(a[i]>val){
a[j]=a[i];break;
}
}
a[i]=val;//將保留在val中的數放到a[i]中
QuickSort(a,i);//遞歸，對前i個數排序
QuickSort(a+i+1,numsize-1-i);//對i+1到numsize這numsize-1-i個數排序
}
}
5. 堆排序 O(n log n)
n個症結字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列知足以下性質（簡稱為堆性質）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），固然，這是小根堆，年夜根堆則換成>=號。//k(i）相當於二叉樹的非葉子結點，K(2i）則是左子節點，k(2i+1）是右子節點.
若將此序列所存儲的向量R[1..n]看作是一棵完整二叉樹的存儲構造，則堆本質上是知足以下性質的完整二叉樹:樹中任一非葉子結點的症結字均不年夜於（或不小於）其閣下孩子（若存在）結點的症結字。
// array是待調劑的堆數組，i是待調劑的數組元素的地位，nlength是數組的長度
//本函數功效是：依據數組array構建年夜根堆
void HeapAdjust(int array[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子結點的地位=2*（父結點地位）+ 1
nChild = 2 * i + 1;
// 獲得子結點中較年夜的結點
if ( nChild < nLength-1 && array[nChild + 1] > array[nChild])
++nChild;
// 假如較年夜的子結點年夜於父結點那末把較年夜的子結點往上挪動，調換它的父結點
if (nTemp < array[nChild])
{
array[i] = array[nChild];
array[nChild]= nTemp;
}
else
// 不然加入輪回
break;
}
}
// 堆排序算法
void HeapSort(int array[],int length)
{
int tmp;
// 調劑序列的前半部門元素，調劑完以後第一個元素是序列的最年夜的元素
//length/2-1是第一個非葉節點，此處"/"為整除
for (int i = floor(length -1)/ 2 ; i >= 0; --i)
HeapAdjust(array, i, length);
// 從最初一個元素開端對序列停止調劑，赓續的減少調劑的規模直到第一個元素
for (int i = length - 1; i > 0; --i)
{
// 把第一個元素和以後的最初一個元故舊換，
// 包管以後的最初一個地位的元素都是在如今的這個序列當中最年夜的
/// Swap(&array[0], &array[i]);
tmp = array[i];
array[i] = array[0];
array[0] = tmp;
// 赓續減少調劑heap的規模，每次調劑終了包管第一個元素是以後序列的最年夜值
HeapAdjust(array, 0, i);
}
}
6.合並排序 O(n log n)
將已有序的子序列歸並，獲得完整有序的序列；即先使每一個子序列有序，再使子序列段間有序。若將兩個 有序表歸並成一個有序表，稱為二路合並。
//合並操作
void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{
int i, j, k;
for(i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)
{
if(sourceArr[startIndex] < sourceArr[i])
{
targetArr[j] = sourceArr[startIndex++];
}
else
{
targetArr[j] = sourceArr[i++];
}
}
if(startIndex <= midIndex)
{
for(k = 0; k <= midIndex-startIndex; k++)
{
targetArr[j+k] = sourceArr[startIndex+k];
}
}
if(i <= endIndex)
{
for(k = 0; k <= endIndex- i; k++)
{
targetArr[j+k] = sourceArr[i+k];
}
}
}
//外部應用遞歸，空間龐雜度為n+logn
void MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex)
{
int midIndex;
int tempArr[100]; //此處年夜小依需求更改
if(startIndex == endIndex)
{
targetArr[startIndex] = sourceArr[startIndex];
}
else
{
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(tempArr, targetArr,startIndex, midIndex, endIndex);
}
}
//挪用
int _tmain(int argc, _TCHAR* argv[])
{
int a[8]={50,10,20,30,70,40,80,60};
int b[8];
MergeSort(a, b, 0, 7);
for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
cout << b[i] << ' ';
cout << endl;
system("pause");
return 0;
}
7.希爾排序 O(n^1.25）
先取一個小於n的整數d1作為第一個增量，把文件的全體記載分紅d1個組。一切間隔為d1的倍數的記載放在統一個組中。先在各組內停止直接拔出排序；然後，取第二個增量d2<d1反復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即一切記載放在統一組中停止直接拔出排序為止。
void ShellSort(int a[], int n){
int d, i, j, temp;
for(d = n/2;d >= 1;d = d/2){
for(i = d; i < n;i++){
temp = a[i];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d){
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}
