經(jīng)典排序算法總結(jié)

最近由于工作上的事情都處理的差不多，手頭沒啥任務(wù)；在就是一直對各種排序算法只有些模糊的概念，上學(xué)那會就沒有好好的學(xué)習(xí)和實際在機上操作過，所以在此特意整理了下這幾個比較經(jīng)典的排序算法，同時也在機上嘗試過幾次都沒問題了，希望對以后會有所幫助，若有不足之處，待改進(jìn)！

別的也不想多說，直接上代碼吧

/*function:交換兩個數(shù)函數(shù)*/
void?swap(int?*num1,?int?*num2)
{
	int?temp;
	
	temp?=?*num1;
	*num1?=?*num2;
	*num2?=?temp;
}

/*
冒泡排序算法
簡單描述：在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩
個數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。
冒泡排序是，算法時間復(fù)雜充0(n2)--[n的平方]?
*/

void?BobbleSort(int?*array,?int?len)
{
	int?i,?j?;
	
	for(i=0;?i=i;?j--)
		{
			if?(array[i]>array[j])
			{
				swap(&array[i],?&array[j]);
			}
		}
	}
}

/*
選擇排序算法
簡單描述：?在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)進(jìn)行交換，然后在剩下
的數(shù)中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止
選擇排序是不穩(wěn)定的，算法復(fù)雜度0(n2)--[n的平方]?
*/
void?SelectSort(int?*array,?int?len)
{
	int?i,?j,?k;
	for(i=0;?i<len;?i++)
	{
		k?=?i;/*給記號賦值*/?
		for(j=i+1;?jarray[j])
			{
				k?=?j;/*是k總是指向最小元素*/?
			}	
		}
		if?(k?!=?i)
		{
			swap(&array[k],?&array[i]);
		}
	}
}

/*
插入排序算法
簡單描述：插入法是一種比較直觀的排序方法，?首先把數(shù)組頭兩個元素排好序，再依次把后面
元素插入適當(dāng)?shù)奈恢茫褦?shù)組元素插完也就完成了排序?
直接插入排序是穩(wěn)定的。算法時間復(fù)雜度0(N2)--[N的平方]?
*/
void?InsertSort(int?*array,?int?len)
{
	int?i,?j,?tmp;
	
	for(i=1;?i=0?&&?array[j]>tmp)?/*從a[i-1]開始找比a[i]小的數(shù)，同時把數(shù)組元素向后移*/?
		{
			array[j+1]?=?array[j];
			j--;
		}
		array[j+1]?=?tmp;/*插入略小的數(shù)到數(shù)組中*/
	}
}

/*
希爾排序算法
簡單描述：首先是把相距k(k>=1)的那幾個元素排好序，再縮小k的值（一般取其一半），再
排序，直到k=1時完成排序
希爾排序是不穩(wěn)定的?
*/?
void?ShellSort(int?*array,?int?len)
{
	int?i,j,?tmp,?k;
	
	k?=?len/2;/*間距值*/
	while(k>=1)
	{
		for(i=k;?i=0?&&?array[j]>tmp)
			{
				array[j+k]?=?array[j];
				j?-=?k;
			}
			array[j+k]?=?tmp;
		}
		k?=?k/2;/*縮小間距值*/
	}
}

/*
快速排序算法
簡單描述：是對冒泡排序的一種本質(zhì)改進(jìn)，基于思想是通過一趟掃描后，使得排序序列的長度
能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序
列的長度可能只減少1，快速排序通過一趟掃描，就能確保某個數(shù)（以它為基準(zhǔn)點吧）的左邊
各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點
的左右只有一個元素為止。
快速排序可以用遞歸實現(xiàn)，也可以用?；膺f歸實現(xiàn)
*/

void?sort(int?*array,?int?min,?int?len)
{
	int?left,?right,?middle;
	int?itmp;
	
	left?=?min;
	right?=?len;
	middle?=?array[(min+len)/2];/*求中間值*/
	do
	{
		while((array[left]<middle)?&&?leftmiddle)?&&?right>min)/*從右邊掃描大于中間值的數(shù)*/
			right--;
		if?(left<=right)
		{
			/*itmp?=?array[left]	;
			array[left]?=?array[right];
			array[right]?=?itmp;*/
			swap(&array[left],?&array[right]);
			left++;
			right--;
		}
	}while(left<=right);
	
	if?(minleft)
	{
		sort(array,?left,?len);
	}
}

void?QuickSort(int?*array,?int?len)
{
	sort(array,?0,?len-1);
}

以下為提供測試算法程序，驗證以上的代碼的正確性：

#define?MAX_LENGTH?20
void?printArray(int?*array)
{
	int?i;
	for(i=0;?i<MAX_LENGTH;?i++)
	{
		if(array[i]?!=?0)
		{
			printf("%d?",?array[i]);
		}
	}
	printf("n");
}

int?main(int?argc,?char?**argv)
{
	int?array[MAX_LENGTH]?=?{9,2,3,1,10,5,8,7,6,4};
	printf("the?array?is:");
	printArray(array);
	
//	BobbleSort(array,?MAX_LENGTH);?//冒泡排序?
	printf("After?Bobble?sort?array?is:");
	printArray(array);
	
//	SelectSort(array,?MAX_LENGTH);?//選擇排序?
	printf("After?Select?sort?array?is:");
	printArray(array);
	
//	InsertSort(array,?MAX_LENGTH);?//插入排序?
	printf("After?Insert?sort?array?is:");
	printArray(array);
	
	ShellSort(array,?MAX_LENGTH);?//希爾排序?
	printf("After?Shell??sort?array?is:");
	printArray(array);
	
//	QuickSort(array,MAX_LENGTH);?//快速排序?
	printf("After?Quict??sort?array?is:");
	printArray(array);
	return?0;
}