几种经典的数据排序及其Java实现(一)

选择排序

思想

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

排序实例


初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76 97

Java实现代码如下：

package selectsort;

public class Sort {
	public static void main(String[] args)
	{
		int[] a = {8,77,66,99,2,7,4,6,100,34};
		int[] b ; 
		b = selectsort(a);
		for(int i  = 0; i < b.length; i++)
		{
			System.out.println(b[i]);
		}
	}
	public static int[] selectsort(int[] p)
	{
		int temp = 0;
		int minindex = 0;
		int[] array = p.clone();
		for(int i = 0; i < array.length; i++)
		{
			minindex = i;
			for(int j = i+1; j < array.length; j++)
			{
				if(array[minindex] > array[j] )
					minindex = j;
			}
			temp = array[i];
			array[i] = array[minindex];
			array[minindex] = temp;
		}
		return array;
	}
}

冒泡法

原理

Java实现代码：

package bubblesort;

public class Bubblesort {
	public static void main(String[] args)
	{
		int[] a = {8,77,66,99,2,7,4,6,100,34};
		int[] b;
		b = bubble(a);
		for(int i =0; i 
  
    array[j+1])
					sway(array,j,j+1);
			}
		}
		return array;
	}
	public static void sway(int[] b, int m, int n)
	{
		int temp = b[m];
		b[m] = b[n];
		b[n] = temp;
	}

}

  

插入排序

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述


一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

Java示例代码如下：

package insertsort;

public class Insert {
	public static void main(String[] args)
	{
		int[] a = {500,77,66,99,2,7,4,6,100,34};
		int[] b;
		b = insert(a);
		for(int i =0; i 
  
   0)&&(array[j - 1] > temp))
				{
					array[j] = array[j - 1];
					j--;
				}
				array[j] = temp; 
			}
		}
		return array;
	}
}

  

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）。