排序演算法

本文對于排序演算法中的直接插入排序、希爾排序、冒泡排序、快速排序和簡單選擇排序給予C語言程式實作，每一種演算法均使用陣列array進行測驗，

一、插入排序

1、直接插入排序

演算法性能分析：

最好情況下時間復雜度	最壞情況下時間復雜度	平均	穩定性
O(n)	O(n2)	O(n2)	穩定
關鍵字在記錄序列中順序有序	關鍵字在記錄序列中逆序有序

C語言實作

#include <stdio.h>//直接插入排序	O(n(2))
int main()
{	int array[]={49,38,65,97,76,99,32,34,21};
	int n=sizeof(array)/sizeof(int); 
	int i,j;
	int temp;
	for(i=1;i<n;i++)
	{	if(array[i-1]>array[i])
		{	temp=array[i];
			j=i-1;
			do
			{	array[j+1]=array[j];
				j--;
			}while(j>=0&&array[j]>temp);
			array[j+1]=temp;
		}
	}
	for(i=0;i<n;i++)
		printf("%d ",array[i]);
}

2、希爾排序

演算法性能分析：

最好情況下時間復雜度	最壞情況下時間復雜度	平均	穩定性
–	–	O(n(1.3))	不穩定

C語言實作

#include <stdio.h>//希爾排序	O(n(1.3))
int main() 
{	int array[]={49,38,65,97,76,99,32,34,21};
	int n=sizeof(array)/sizeof(int); 
	int i,j;
	int temp,d=n/2;
	while(d>0)
	{	for(i=d;i<n;i++)
		{	temp=array[i];
			j=i-d;
			while(j>=0&&array[j]>temp)
			{	array[j+d]=array[j];
				j=j-d;
			}
			array[j+d]=temp;
		}
		d=d/2;
	}
	for(i=0;i<n;i++)
		printf("%d ",array[i]);
}

二、交換排序

1、冒泡排序

演算法性能分析：

最好情況下時間復雜度	最壞情況下時間復雜度	平均	穩定性
O(n)	O(n2)	O(n2)	穩定
正序（只需要進行一趟冒泡）	逆序（需要進行n-1趟冒泡）

C語言實作

#include<stdio.h>	//冒泡排序 O(n(2))
int main(){
	int array[]={49,38,65,97,76,99,32,34,21},i,j,temp,swap=1;
	int n=sizeof(array)/sizeof(int); 
	while(swap!=0){
		swap=0;
		for(j=0;j<n-1;j++)
			if(array[j]>array[j+1]){
				temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
				swap=1;
			} 
	}
	for(i=0;i<n;i++)
		printf("%d ",array[i]);
}

2、快速排序

演算法性能分析：

最好情況下時間復雜度	最壞情況下時間復雜度	平均	穩定性
O(nlog2(n))	O(n2)	O(nlog2(n))	不穩定
完全無序的情況下	關鍵字在記錄序列中逆序有序

C語言實作

#include <stdio.h> //快速排序	O(nlog2n)
#include <stdlib.h>
int Partition(int *array,int low,int high)
{	int pivotkey=array[low];
	while(low<high)
	{	while(low<high && array[high]>=pivotkey)
			--high;
		array[low]=array[high];
		while(low<high && array[low]<pivotkey)
			++low;
		array[high]=array[low];
	} 
	array[low]=pivotkey;
	return low;
}
void QSort(int *array,int low,int high)
{	if(low<high)
	{	int pivotloc=Partition(array,low,high);
		QSort(array,low,pivotloc-1);
		QSort(array,pivotloc+1,high);
	}
}
void Print(int *array,int size)
{	for(int i=0;i<size;i++)
		printf("%d ",array[i]);
	return;
}
int main()
{	int array[]={49,38,65,97,76,99,32,34,21};
	int size=sizeof(array)/sizeof(int);
	QSort(array,0,size-1);
	Print(array,size);
	return 0;
}

三、選擇排序

演算法性能分析：

最好情況下時間復雜度	最壞情況下時間復雜度	平均	穩定性
O(n2)	O(n2)	O(n2)	不穩定

（時間復雜度與原始序列無關）

C語言實作

1、簡單選擇排序

#include<stdio.h>  //簡單選擇排序 O(n(2))
int main(){
	int array[]={49,38,65,97,76,99,32,34,21},i,j,min,temp;
	int n=sizeof(array)/sizeof(int); 
	for(i=0;i<n-1;i++){
		min=i;
		for(j=i+1;j<10;j++)
			if(array[j]<array[min])min=j;
		if(min!=i){
			temp=array[i];
			array[i]=array[min];
			array[min]=temp;
		}
	}
	for(i=0;i<n;i++)
		printf("%d ",array[i]);
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/244004.html

標籤：其他

上一篇：linux下/proc/pid/maps和pmap命令詳解

下一篇：SOS