資料結構學習筆記 排序

插入排序

時間複雜度：O(n2) 穩定

将序列分為已排好和未排好的兩個部分，對未排序部分的第一個元素與排好部分的每個元素進行比較，若小于則交換位置

//插入排序 
void insertionSort(int a[],int n){
	int tmp,i,j;
	for(i=1;i<n;i++){
		tmp=a[i];
		for(j=i;j>0&&a[j-1]>tmp;j--){
			a[j]=a[j-1];
		}
		a[j]=tmp;
	}
}
           

選擇排序

時間複雜度：O(n2) 不穩定

周遊數組，周遊到i時，a0,a1…ai-1是已排好序的，然後從i到n選擇出最小的，記錄下位置，如果不是第i個，則和第i個元素交換。

//選擇排序
void selectionSort(int b[],int n){
	int i,j,p,tmp;
	for(i=0;i<n-1;i++){
		p=i;
		for(j=i+1;j<n;j++){
			if(b[p]>b[j])
				p=j;
	
		}
		if(p!=i){
			tmp=b[i];
			b[i]=b[p];
			b[p]=tmp;
		}
	}
}
           

冒泡排序

時間複雜度：O(n2) 穩定

相鄰兩個元素進行比較，若前者大于後者則交換位置

//冒泡排序
void bubbleSort(int c[], int n){
	int i=n;
	int tmp;
	while(i){
		for(int j=0;j<i-1;j++){
			if(c[j]>c[j+1]){
				tmp=c[j];
				c[j]=c[j+1];
				c[j+1]=tmp;
			}
		}
		i--;
	}
}
           

希爾排序

時間複雜度：O(nlogn) 不穩定

将待排序的一組元素按一定間隔分為若幹個序列，分别進行插入排序，在每輪排序中間隔逐漸變小，直至間隔為1

//希爾排序
void shellSort(int d[], int n)
{
    int k,i,j,temp; 
    for(k=n/2;k>=1;k=k/2)
    {
        for(i=k;i<n;i++)
        {
            temp=d[i];
            for(j=i-k;j>=0&&d[j]>temp;j=j-k)
            {
                d[j+k]=d[j];
            }
        d[j+k]=temp;
        }
    }
}
           

主函數

int main(){
	int a[5]={4,7,6,34,23};
	insertionSort(a,5);
	printf("插入排序:");
	for(int i=0;i<5;i++) printf(" %d",a[i]);
	printf("\n"); 
    int b[5]={9,38,25,43,10};
	selectionSort(b,5);
	printf("選擇排序:");
	for(int i=0;i<5;i++) printf(" %d",b[i]);
	printf("\n"); 
	int c[5]={45,21,56,43,23};
	bubbleSort(c,5);
	printf("冒泡排序:");
	for(int i=0;i<5;i++) printf(" %d",c[i]);
	printf("\n"); 
	int d[5]={5,8,34,27,21};
	shellSort(d,5);
	printf("希爾排序:");
	for(int i=0;i<5;i++) printf(" %d",d[i]);
}
           

運作結果