冒泡排序

---

前言       

          冒泡排序算法运行起来非常慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。

冒泡排序的思想

比较相邻两个数据。如果左边的队员高，则两数据交换位置。向右移动一个位置，比较下面两个数据。

冒泡排序的Java核心代码

public static void bubbleSort(List<Integer> lists) { for(int i=lists.size()-1; i>1; i--) { for(int j=0; j<i; j++) { if(lists.get(j) > lists.get(j+1)) { Integer temp = lists.get(j+1); lists.set(j+1,lists.get(j)); lists.set(j,temp); } } } }

冒泡排序的效率

         交换和比较操作次数都和N²成正比。

选择排序

---

前言        

          选择排序改进了冒泡排序，将必要的交换次数从O(N²)减少到O(N)。不幸的是比较次数仍保持为O(N²)。然而，选择排序仍然为大记录量的排序提出了一个非常重要的改进，因为这些大量的记录需要在内存中移动，这就使交换的时间和比较的时间相比起来，交换的时间更为重要。

选择排序的规则

         第一个元素和后面的元素全部比较，找出最小的元素，并和第一个元素交换。

选择排序的核心Java代码

public static void selectionSort(List<Integer> lists) { for(int i=0; i<lists.size()-1; i++) { for(int j=i+1; j<lists.size(); j++) { if(lists.get(i) > lists.get(j)) { Integer temp = lists.get(j); lists.set(j,lists.get(i)); lists.set(i,temp); } } } }

选择排序的效率

          比较操作次数和N ²成正比，交换操作次数和N成正比。

插入排序

---

前言       

          在大多数情况下，插入排序算法是基本排序算法中最好的一种。虽然插入排序算法仍然需要 O(N²)的时间，但是在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点。尽管它比冒泡排序算法和选择排序算法都更麻烦一些，但它也并不很复杂。它经常被用在较复杂的排序算法的最后阶段，例如快速排序。

插入排序的规则

         局部有序，被标记的元素左边都是有序的。

插入排序的核心Java代码

public static void insertSort(List<Integer> lists) { for(int i=1; i<lists.size(); i++) { Integer temp = lists.get(i); int j=i; while(j>0 && lists.get(j-1)>temp) { lists.set(j, lists.get(j-1)); --j; } lists.set(j, temp); } }

插入排序的效率

            比较操作次数和N ²成正比，交换操作次数和N成正比。

几种简单排序之间的比较

---

除非手边没有算法书可参考，一般情况几乎不太使用冒泡排序算法。它过于简单了，以至于可以毫不费力地写出来。然而当数据量很小的时候它会有些应用的价值。 选择排序虽然把交换次数降到了最低，但比较的次数仍然很大。当数据量很小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。 在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择。对于更大数据量的排序来说，快速排序通常是最快的方法。