java实现 多种排序算法//插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通
java实现 多种排序算法
//插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
//插入排序都采用in-place在数组上实现。具体算法描述如下：//从第一个元素开始，该元素可以认为已经被排序//取出下一个元素，在已经排序的元素序列中从后向前扫描//如果该元素（已排序）大于新元素，将该元素移到下一位置//重复步骤3，直到找到已排序的元素小于或者等于新元素的位置//将新元素插入到该位置中//重复步骤2~5public class 插入排序 {public static void main(String[] args) {int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };insert(array);
for (int arr : array) {System.out.print(arr + " ");}}
public static void insert(int[] array) {for (int i = 0; i+1 < array.length; i++) {int temp = array[i+1];for (int j = i; j >= 0; j--) {if (array[j] > temp) {exchange(array, j, j + 1);} else {array[j + 1] = temp;break;}}}}
public static void exchange(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}
//归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。//归并操作的过程如下：//申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列//设定两个指针，最初位置分别为两个已经排序序列的起始位置//比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置//重复步骤3直到某一指针达到序列尾//将另一序列剩下的所有元素直接复制到合并序列尾public class 归并排序 {public static void main(String[] args) {int[] arrayA = new int[] { 9, 16, 25, 35, 46, 49, 76, 85, 93 };int[] arrayB = new int[] { 4, 14, 24, 34, 44, 54, 65, 76, 84, 93, 102, 116 };int[] arrayC = merge(arrayA, arrayB);
for (int arr : arrayC) {System.out.print(arr + " ");}}
public static int[] merge(int[] arrayA, int[] arrayB) {int[] arrayC = new int[arrayA.length + arrayB.length];int a = 0, b = 0,c=0;while(a < arrayA.length && b < arrayB.length) {if(arrayA[a]<arrayB[b]){arrayC[c++]=arrayA[a++];}else{arrayC[c++]=arrayB[b++];}}if(arrayA.length<arrayB.length){while(b<arrayB.length){arrayC[c++]=arrayB[b++];}}else{while(a<arrayA.length){arrayC[c++]=arrayA[a++];}}
return arrayC;}
public static void exchange(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}
//快速排序(Quick Sort)：使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。//步骤为：//从数列中挑出一个元素，称为 "基准"（pivot），//重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。//递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。?public class 快速排序 {public static void main(String[] args) {int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };quick(array, 0,array.length-1);
for (int i : array) {System.out.print(i + " ");}}public static void quick(int[] array, int first,int high){int pivot=partition(array, first, high);if(first<pivot-1){quick(array, first, pivot-1);}if(high>pivot+1){quick(array,pivot+1,high);}}
//逆序找到一个小于pivot的数，正序找到一个大于pivot的数，交换。最后再将pivot交换到中间位置。public static int partition(int[] array, int first,int high) {int low=first+1;while(high>low){if(array[high]>=array[first]){high--;}else if(array[low]<=array[first]){low++;}else{exchange(array, high, low);high--;//这样才有可能high==low}}if(array[high]<array[first]){exchange(array, first, high);}return high;}public static void exchange(int[] array,int i,int j){int temp=array[i];array[i]=array[j];array[j]=temp;}}
//冒泡排序(Bubble Sort)：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。?//冒泡排序算法的运作如下：//比较相邻的元素。如果第一个比第二个大，就交换他们两个。//对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。//针对所有的元素重复以上的步骤，除了最后一个。//持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。public class 冒泡排序 {public static void main(String[] args) {int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };bubble(array);
for (int arr : array) {System.out.print(arr + " ");}}
public static void bubble(int[] array) {for (int i = array.length; i >0; i--) {for (int j = 0; j < i-1; j++) {if (array[j] > array[j+1]) {exchange(array, j, j+1);}}}}
public static void exchange(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}
//希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。//希尔排序是基于插入排序的以下两点性质而提出改进方法的：//插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率//但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位.//步长gap的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。//Donald Shell 最初建议步长选择为并且对步长取半直到步长达到 1。public class 希尔排序 {public static void main(String[] args) {int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };shell(array);
for (int arr : array) {System.out.print(arr + " ");}}
public static void shell(int[] array) {int gap=array.length/2;do{insert(array, gap);gap=gap/2;}while(gap>0);}public static void insert(int[] array,int gap) {for (int i = 0; i+gap < array.length; i++) {int temp = array[i+gap];for (int j = i; j >= 0; j-=gap) {if (array[j] > temp) {exchange(array, j, j + gap);} else {array[j + gap] = temp;break;}}}}
public static void exchange(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}
//选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾(目前已被排序的序列)。以此类推，直到所有元素均排序完毕。public class 选择排序 {public static void main(String[] args) {int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };select(array);
for (int arr : array) {System.out.print(arr + " ");}}
public static void select(int[] array) {for (int i = 0; i < array.length; i++) {for (int j = i + 1; j < array.length; j++) {if (array[i] > array[j]) {exchange(array, i, j);}}}}
public static void exchange(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}
都是自己写的，欢迎拍砖!
排序方法的选择
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要?(1)若n较小，可采用直接插入或直接选择排序。?当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；?但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。?这两种都是稳定排序算法。?
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。?
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。?快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；?堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。? 归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。?
(4)特殊的箱排序、基数排序?它们都是一种稳定的排序算法，但有一定的局限性：?1>关键字可分解。?2>记录的关键字位数较少，如果密集更好?3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序?
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序?
在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是： 插入排序?
排序的平均时间复杂度为O(n?logn)的算法是：归并排序、快速排序、堆排序?
排序的平均时间复杂度为O(n?n)的算法是：冒泡排序、插入排序、选择排序?
排序过程中的比较次数与排序方法无关的是：选择排序、归并排序?
如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，最快的算法是：堆排序?
在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法：插入排序?
