选择,插入,交换,冒泡,希尔排序算法的效率比较

#include#includeusing namespace std;templatevoid bubbleSort(T arr[],int n){ int temp,i,j; bool flag=false; for(i=0;iarr[j]) { temp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; flag=true; } if(!flag) break; }}void xuanzeSort(int arr[],int n){ int smallIndex; int pass,j; int temp; for(pass=0;passvoid swapSort(T arr[],int n){ int i,j,temp; for(i=0;ivoid shellSort(T arr[],int n){ int i,j,gap=n; T temp; do { gap=gap/3+1;//间隔 for(i=gap;i=0&&temp1);//间隔}templatevoid insertionSort(T arr[],int n){ int i,j; T target; for(i=1;i0&&target<3;j++) {="" switch(j)="" {="" case="" 0:=""><><><><><><><'timing the="" selection=""><'selection sort="" takes=""><><'><'timing the="" bubble=""><'bubble sort="" takes=""><><'><'timing the="" insert=""><'insert sort="" takes=""><><'><'timing the="" swap=""><'swap sort="" takes=""><><'><'timing the="" shell=""><'shell sort="" takes=""><><'>

对10000个数据排序的时间效率结果,最好是希尔排序,最差是交换排序,最好最坏情况的时间效率相差不大,从这里可以看出为什么算法宁愿找个最差情况比较好的算法也不要平均情况比较好的算法.

随机数
Timing the Selection Sort
Selection Sort takes 130 seconds.
Timing the Bubble Sort
Bubble Sort takes 130 seconds.
Timing the Insert Sort
Insert Sort takes 60 seconds.
Timing the Swap Sort
Swap Sort takes 280 seconds.
Timing the Shell Sort
Shell Sort takes 10 seconds.

正序数
Timing the Selection Sort
Selection Sort takes 120 seconds.
Timing the Bubble Sort
Bubble Sort takes 120 seconds.
Timing the Insert Sort
Insert Sort takes 60 seconds.
Timing the Swap Sort
Swap Sort takes 290 seconds.
Timing the Shell Sort
Shell Sort takes 10 seconds.

倒序数
Timing the Selection Sort
Selection Sort takes 120 seconds.
Timing the Bubble Sort
Bubble Sort takes 120 seconds.
Timing the Insert Sort
Insert Sort takes 60 seconds.
Timing the Swap Sort
Swap Sort takes 290 seconds.
Timing the Shell Sort
Shell Sort takes 0 seconds.