- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- void BubbleSort1 (int n, int *array) /*little > big*/
- {
- int i, j;
- for (i=0; i<n-1; i++)
- {
- for (j=n-1; j>i; j--)
- {
- if (array[j] < array[j-1])
- {
- int temp = array[j];
- array[j] = array[j-1];
- array[j-1] = temp;
- }
- }
- }
- }
- void BubbleSort2 (int n, int *array)
- {
- int i, j, flag=1; /*flag=1表示需要继续冒泡*/
- for (i=0; i<n-1 && flag; i++)
- {
- flag = 0;
- for (j=n-1; j>i; j--)
- {
- if (array[j] < array[j-1])
- {
- int temp = array[j];
- array[j] = array[j-1];
- array[j-1] = temp;
- flag = 1;
- }
- }
- }
- }
- void SelectSort (int n, int *array)
- {
- int i, j, min;
- for (i=0; i<n-1; i++)
- {
- min = i;
- for (j=i+1; j<n; j++)
- {
- if (array[min] > array[j])
- min = j;
- }
- int temp = array[min];
- array[min] = array[i];
- array[i] = temp;
- }
- }
- void InsertSort (int n, int*array)
- {
- int i, j;
- for (i=1; i<n; i++)
- {
- if (array[i] < array[i-1]) /*是否需要插入*/
- {
- int key = array[i]; //哨兵
- for (j = i-1;j>=0 && array[j] > key; j--)
- {
- array[j+1] = array[j];
- }
- /*循环结束时array[j]<=key,将key插入到j+1处*/
- array[j+1] = key;
- }
- }
- }
- /*分组插入排序*/
- void ShellSort (int n, int *array)
- {
- int i, j;
- int increment;
- for (increment=n/2; increment > 0; increment /= 2)
- {
- for (i=0; i<increment; i++) /*下面对一组序列进行插入排序*/
- {
- for (j=i+increment; j<n; j+=increment)
- {
- if (array[j] < array[j-increment])
- {
- int key = array[j];
- int k;
- for (k=j-increment; k>=0 && array[k]>key; k -= increment)
- {
- array[k+increment] = array[k];
- }
- array[k+increment] = key;
- }
- }
- }
- }
- }
- /*分治法*/
- void QuickSort (int left, int right, int *array)
- {
- if(left>=right)
- return ;
- int i=left, j=right;
- int key=array[i];
- while (i<j)
- {
- while (i<j && array[j]>=key)
- j--;
- array[i] = array[j];
- while (i<j && array[i]<=key)
- i++;
- array[j] = array[i];
- }
- array[i] = key;
- QuickSort(left, i-1, array);
- QuickSort(i+1, right, array);
- }
- /*array[start+1] ~ array[end]已经满足堆的定义,调整使得array[start] ~ array[end]满足堆定义*/
- void HeapAdjust (int start, int end, int array[])
- {
- int i;
- int temp = array[start]; /*产生第一个空白*/
- for (i=2*start+1; i<=end; i=2*i+1) /*每次循环时空白节点为array[(i-1)/2]*/
- {
- if (i<end && array[i] < array[i+1]) /*在左右孩子中寻找较大值*/
- i++;
- if (array[i] > temp)
- array[(i-1)/2] = array[i];
- else
- break;
- }
- array[(i-1)/2] = temp; /*插入原来的temp到空白处*/
- }
- void HeapSort (int n, int array[])
- {
- int i;
- for (i=(n-2)/2; i>=0; i--) /*构造大顶堆*/
- HeapAdjust(i, n-1, array);
- for (i=n-1; i>0; i--)
- {
- int t = array[i]; /*将根节点交换到数组末端*/
- array[i] = array[0];
- array[0] = t;
- HeapAdjust(0, i-1, array); /*重新调整堆*/
- }
- }
- /*array[s…m]和array[m+1…t]均已各自有序,合并使得array[s…t]有序*/
- void Merge(int s, int m, int t, int *array)
- {
- int temp[t-s+1];
- int i=s, j=m+1, k=0;
- while(i<=m && j<=t)
- {
- if(array[i] < array[j])
- temp[k++] = array[i++];
- else
- temp[k++] = array[j++];
- }
- while(i<=m)
- temp[k++] = array[i++];
- while(j<=t)
- temp[k++] = array[j++];
- for(i=s, k=0; i<=t && k<=t-s; i++, k++)
- {
- array[i] = temp[k];
- }
- }
- void MSort (int s, int t, int *array) /*递归调用*/
- {
- if(s == t)
- return ;
- int m = (s+t)/2;
- MSort(s, m, array);
- MSort(m+1, t, array);
- Merge(s, m, t, array);
- }
- void MergeSort1(int n, int *array)
- {
- MSort(0, n-1, array);
- }
- void MergeSort2(int n, int *array) /*非递归实现归并排序*/
- {
- int k, i;
- for (k=1; 2*k<n; k *= 2) /*设置每段待归并的有序序列的长度:1,2,4,8,16……*/
- {
- for (i=0; i+k-1<n; i += 2*k) /*考虑待归并的左右两段序列,[i+k-1]是左序列末尾元素下标*/
- { /*[end=i+2*k-1]是右序列末尾元素下标,end不应该超过n-1*/
- int end=i+2*k-1;
- if(end > n-1)
- end = n-1;
- Merge(i, i+k-1, end, array);
- }
- }
- }
- int main()
- {
- long start, stop;
- int n;
- printf("下面比较几个时间复杂度为NlogN的排序算法效率高低,其他3个低效率的排序就不考虑了\\n");
- printf("输入待排序数量(int类型表示,在我的机器上超过100万就可能溢出):\\n");
- scanf("%d", &n);
- int a[n], i;
- for(i=0; i<n; i++)
- a[i] = rand()%n;
- start = clock();
- ShellSort(n, a);
- stop = clock();
- printf("希尔排序%d个数据花费时间为: %ldms\\n", n, (stop-start)*1000/CLOCKS_PER_SEC);
- for(i=0; i<n; i++)
- a[i] = rand()%n;
- start = clock();
- HeapSort(n, a);
- stop = clock();
- printf("堆排序%d个数据花费时间为: %ldms\\n", n, (stop-start)*1000/CLOCKS_PER_SEC);
- for(i=0; i<n; i++)
- a[i] = rand()%n;
- start = clock();
- MergeSort1(n, a);
- stop = clock();
- printf("递归式归并排序%d个数据花费时间为: %ldms\\n", n, (stop-start)*1000/CLOCKS_PER_SEC);
- for(i=0; i<n; i++)
- a[i] = rand()%n;
- start = clock();
- MergeSort2(n, a);
- stop = clock();
- printf("非递归式归并排序%d个数据花费时间为: %ldms\\n", n, (stop-start)*1000/CLOCKS_PER_SEC);
- for(i=0; i<n; i++)
- a[i] = rand()%n;
- start = clock();
- QuickSort(0, n-1, a);
- stop = clock();
- printf("快速排序%d个数据花费时间为: %ldms\\n", n, (stop-start)*1000/CLOCKS_PER_SEC);
- /* for(i=0; i<n; i++)
- {
- printf("%d ", a[i]);
- }
- */
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1410201410626.html
来源: http://www.codesnippet.cn/detail/1410201410626.html