目录

题目描述冒泡排序法思路代码特点 插入排序法思路代码特点 希尔排序思路代码特点 选择排序思路代码特点 堆排序思路代码特点 归并排序思路代码特点:

题目描述

给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：只有1个元素；数据2：11个不相同的整数，测试基本正确性；数据3：103个随机整数；数据4：104个随机整数；数据5：105个随机整数；数据6：105个顺序整数；数据7：105个逆序整数；数据8：105个基本有序的整数；数据9：105个随机正整数，每个数字不超过1000。

输入格式: 输入第一行给出正整数N（≤100000​​ ），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。

输出格式: 在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例:

11 4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 981

冒泡排序法

思路

i从0开始递增，如果第i个元素小于后一个元素，就交换它们的位置，这样可以让最大的元素移动到最后。然后让次大的元素移动到倒数第二个位置，一直循环。

代码

void Bubble_Sort( int A[], int N ) { int P, i; for( P=N-1; P>=0; --P ){ int flag = 0; for( i=0; i<P; ++i ){ if( A[i]>A[i+1] ){ Swap(&A[i], &A[i+1]); flag = 1; } } if( flag==0 )break; } }

特点

时间复杂度:最好情况（顺序）T=O(N)；最坏情况(逆序） T=O(N²) 稳定性:稳定 。

插入排序法

思路

前面i-1个元素是有序的，插入第i个元素，寻找合适的位置，让这i个元素也是有序的。

代码

void Insertion_Sort( int A[], int N ) { int temp, i, P; for( P=1; P<N; ++P ){ temp = A[P]; for( i=P; i>=1; --i ){ if( temp>=A[i-1] ){ A[i] = temp; break; } else{ A[i] = A[i-1]; if(i==1) A[0] = temp; } } } }

特点

时间复杂度:最好情况（顺序）T=O(N)；最坏情况(逆序） T=O(N²) 稳定性:稳定 关于逆序对:冒泡排序法和插入排序法每次都消除一个 逆序对，所以其时间复杂度和数据规模以及逆序对的数量I有关。T(N,I)=O(N,I).所以如果元素基本有序，那么插入排序是简单且高效的。 任意N个不同元素组成的序列平均有N(N-1)/4个逆序对，所以如果仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ω(N²)。

希尔排序

思路

第一行相同颜色数字的间隔为5，每一种颜色单独进行插入排序。然后间隔为3，每一种颜色单独进行插入排序。最后间隔为1进行排序，相当于一次插入排序。

代码

void Shell_Sort(int A[], int N) { int D, P, i, temp; for( D=N/2; D>0; D/=2 ) for( P=D; P<N; ++P ){ temp = A[P]; for( i=P; i>=D; i-=D ){ if( temp >=A[i-D] ){ A[i] = temp; break; } else{ A[i] = A[i-D]; if(i-2*D<0) A[i-D] = temp; } } } }

特点

时间复杂度:如果增量序列是D=N/2，然后每次D除以2，最坏情况是T=θ(N²)。原因是相邻的D不互质，小的D可能不会发挥作用。 使用其他的增量序列，Hibbard序列和Sedgewick序列可以有效减小时间复杂度。 稳定性:不稳定。比如2 10 8 8，在增量元素是2，也就是间隔为2进行排序时，第二个8会和10交换位置，导致两个8的相对位置也发生了变化。

选择排序

思路

找到未排序部分的最小元素，换到先前有序部分的末尾后一个，此时有序部分多了一个元素，未排序部分少了一个元素。

代码

int ScanForMin(int A[], int i, int N) { int Minj=i, j, Min=A[i]; for( j=i; j<=N; ++j ) if(A[j]<Min){ Minj = j; Min = A[j]; } return Minj; } void Selection_Sort(int A[], int N) { int i, MinPosition; for( i=0; i!=N; ++i ) { MinPosition = ScanForMin(A, i, N-1); Swap(&A[i], &A[MinPosition]); } }

特点

时间复杂度:用直接扫描所有元素的方式找最小，时间复杂度为T=θ(N²) 稳定性:不稳定。比如序列5 8 5 2 9，第一次扫描最小是2,2将和第一个5进行交换，这样两个5的相对位置发生了改变。

堆排序

思路

1.最小堆排序。建立最小堆，每次弹出根结点元素到临时数组，最后再把临时数组的元素都复制回原来的数组。 2.最大堆排序。建立最大堆，然后将最大堆头结点和最后一个结点交换，也就是把最大元素放到了数组的尾巴上。

代码

void PercDown( int A[], int i, int N ) { int parent, child; int x; x = A[i]; for(parent=i;parent*2+2<=N;parent=child){ child = parent*2+1; if(child!=N-1&&A[child]<A[child+1]) ++child; if(x>A[child]) break; else A[parent] = A[child]; } A[parent] = x; } void Heap_Sort(int A[], int N) { int i; for( i=N/2-1; i>=0; --i ) PercDown( A, i, N ); for( i=N-1; i>0; --i ){ Swap( &A[0], &A[i] ); PercDown( A, 0, i ); } }

特点

时间复杂度:最小堆排序需要临时数组，复制数据也需要时间。T(N)=O(NlogN) 最大堆排序平均时间复杂度为2NlogN-O(NloglogN)，可以看出比NlogN小一点 稳定性：不稳定。比如序列1 7 3 7，整理成最大堆时，第一个7会到堆顶，然后会被换到数组末尾，这样两个7的相对位置就发生了改变。

归并排序

思路

基本思想是把两个有序序列归并成一个有序序列。如果采用递归算法，就是将一整个序列分成左右两个，先把左右序列都调整成有序的，然后归并左右序列。如果采用非递归算法，使用一个变量length，先归并length=1的序列，然后归并length=2的序列，一直到length大于N.

代码

递归算法:

void Merge(int A[], int *temp, int L, int R, int RightEnd) { int LeftEnd = R - 1, tmp = L, Num = RightEnd - L + 1, i; while( L <= LeftEnd && R <= RightEnd ){ if( A[L] <= A[R] ) temp[tmp++] = A[L++]; else temp[tmp++] = A[R++]; } while( L <= LeftEnd ) temp[tmp++] = A[L++]; while( R <= RightEnd ) temp[tmp++] = A[R++]; for( i=0; i<Num; ++i,--RightEnd ) A[RightEnd] = temp[RightEnd]; } void MSort(int A[], int *temp, int L, int RightEnd) { int center; if( L < RightEnd ){ center = (L + RightEnd) / 2; MSort( A, temp, L, center ); MSort( A, temp, center+1, RightEnd ); Merge( A, temp, L, center+1, RightEnd ); } } void Merge_Sort1(int A[], int N) { int *temp; temp = (int*)malloc(N*sizeof(int)); if(temp!=NULL){ MSort(A, temp, 0, N-1); free(temp); } }

非递归算法:

void Merge(int A[], int *temp, int L, int R, int RightEnd) { int LeftEnd = R - 1, tmp = L, Num = RightEnd - L + 1, i; while( L <= LeftEnd && R <= RightEnd ){ if( A[L] <= A[R] ) temp[tmp++] = A[L++]; else temp[tmp++] = A[R++]; } while( L <= LeftEnd ) temp[tmp++] = A[L++]; while( R <= RightEnd ) temp[tmp++] = A[R++]; for( i=0; i<Num; ++i,--RightEnd ) A[RightEnd] = temp[RightEnd]; } void Merge_pass(int A[], int *temp, int N, int length) { int i, j; for( i=0; i<=N-2*length; i+=2*length ) Merge( A, temp, i, i+length, i+2*length-1 ); if( i+length < N ) Merge( A, temp, i, i+length, N-1 ); else for( j=i; j!=N; ++j ) temp[j] = A[j]; } void Merge_sort2(int A[], int N) { int length; int *temp; length = 1; temp = (int *)malloc(N*sizeof(int)); if( temp!=NULL ){ while( length < N ){ Merge_pass( A, temp, N, length ); length *= 2; Merge_pass( temp, A, N, length ); length *= 2; } free( temp ); } }

特点:

时间复杂度:T(N)=O(NlogN) 稳定性:稳定