2.1.5 排序[3]
各种排序算法以及它们的时间复杂度。
排序算法有很多,包括插入排序、冒泡排序、堆排序、归并排序、选择排序、计数排序、基数排序、桶排序、快速排序等。插入排序、堆排序、选择排序、归并排序、快速排序和冒泡排序都是比较排序,堆排序属于选择排序,插入排序、希尔排序属于插入排序。下面复习几种常考的排序算法。
1.冒泡排序(BubbleSort)
最简单的一个冒泡排序算法如下。
public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() |
上面冒泡排序算法的效率为:O(N2)
2.选择排序(SelectSort)
public void selectionSort() { int out, in, min; for(out=0; out<nElems-1; out++) // outer loop { min = out; // minimum for(in=out+1; in<nElems; in++) // inner loop if(a[in] < a[min] ) // if min greater, min = in; // we have a new min swap(out, min); // swap them } // end for(out) } // end selectionSort() |
上述排序算法的效率为:O(N2)
3.插入排序(InsertSort)
在插入排序中,一组数据在某个时刻是局部有序的,而在冒泡和选择排序中是完全有序的。
public void insertionSort() { int in, out; for(out=1; out<nElems; out++) // out is dividing line { long temp = a[out]; // remove marked item in = out; // start shifts at out while(in>0 && a[in-1] >= temp) // until one is smaller, { a[in] = a[in-1]; // shift item to right --in; // go left one position } a[in] = temp; // insert marked item } // end for } // end insertionSort() |
上述排序算法的效率比冒泡排序快一倍,比选择排序略快,但也是O(N2)。如果数据基本有序,几乎需要O(N)的时间。
版权声明:51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。