java实现 多种排序算法

//冒泡排序(Bubble Sort)：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。 

//冒泡排序算法的运作如下：

//比较相邻的元素。如果第一个比第二个大，就交换他们两个。

//对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

//针对所有的元素重复以上的步骤，除了最后一个。

//持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

public class 冒泡排序 {

public static void main(String[] args) {

int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };

select(array, 0, array.length);

for (int arr : array) {

System.out.print(arr + " ");

}

}

public static void bubble(int[] array, int first, int high) {

for (int i =  high -1; i > first; i--) {

for (int j =  first; 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;

}

}

//改进的冒泡，加入flag，减少不必要的交换

public static void bubble(int[] array, int first, int high) {

boolean flag = true;

for (int i = first; i < high && flag; i++) {

flag = false;

for (int j = high-1; j > first; j--) {

if (array[j] < array[j - 1]) {

flag = true;

exchange(array, j, j - 1);

}

}

}

}

时间复杂度O(n2).

//选择排序(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, 0, array.length);

for (int arr : array) {

System.out.print(arr + " ");

}

}

public static void select(int[] array, int first, int high) {

int min;

for (int i = first; i < high; i++) {

min = i;

for (int j = i + 1; j < high; j++) {

if (array[min] > array[j]) {

min = j;

}

}

if (min != i) {

exchange(array, min, i);

}

}

}

public static void exchange(int[] array, int i, int j) {

int temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

时间复杂度O(n2).但交换移动数据的次数比冒泡排序少。

 

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

//插入排序都采用in-place在数组上实现。具体算法描述如下：

//从第一个元素开始，该元素可以认为已经被排序

//取出下一个元素，在已经排序的元素序列中从后向前扫描

//如果该元素（已排序）大于新元素，将该元素移到下一位置

//重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

//将新元素插入到该位置中

//重复步骤2~5

public class 插入排序 {

public static void main(String[] args) {

int[] array = new int[] { 16, 25, 76, 49, 85, 35, 46, 93, 9 };

insert(array, 0, array.length);

for (int i : array) {

System.out.print(i + " ");

}

}

public static void insert(int[] array, int first, int high) {

for (int i = first + 1; i < high; i++) {

if (array[i] < array[i - 1]) {

int j;

int temp = array[i];// 哨兵

for (j = i - 1; j >= 0 && array[j] > temp; j--) {

array[j + 1] = array[j];// 后移

}

array[j + 1] = temp;

}

}

}

}

平均比较和移动次数为n平方/4，即时间负责度为O(n2)，但插入比冒泡和选择的性能要好。

//归并操作(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;

}

}

//希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。

//希尔排序是基于插入排序的以下两点性质而提出改进方法的：

//插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

//但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位.

//步长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;

}

}

基数排序：

基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

基数排序的时间复杂度是 O(k·n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n))，因为k的大小一般会受到 n 的影响。 

以LSD为例，假设原来有一串数值如下所示：

　　73, 22, 93, 43, 55, 14, 28, 65, 39, 81

　　首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

　　0

　　1 81

　　2 22

　　3 73 93 43

　　4 14

　　5 55 65

　　6

　　7

　　8 28

　　9 39

　　接下来将这些桶子中的数值重新串接起来，成为以下的数列：

　　81, 22, 73, 93, 43, 14, 55, 65, 28, 39

　　接着再进行一次分配，这次是根据十位数来分配：

　　0

　　1 14

　　2 22 28

　　3 39

　　4 43

　　5 55

　　6 65

　　7 73

　　8 81

　　9 93

　　接下来将这些桶子中的数值重新串接起来，成为以下的数列：

　　14, 22, 28, 39, 43, 55, 65, 73, 81, 93

　　这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

　　LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

都是自己写的，欢迎拍砖!

排序方法的选择

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要 

(1)若n较小，可采用直接插入或直接选择排序。 

当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数； 

但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。 

这两种都是稳定排序算法。 

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。 

(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 

堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。 

　归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。 

(4)特殊的箱排序、基数排序 

它们都是一种稳定的排序算法，但有一定的局限性： 

1>关键字可分解。 

2>记录的关键字位数较少，如果密集更好 

3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序 
在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是： 插入排序 
排序的平均时间复杂度为O(n•logn)的算法是：归并排序、快速排序、堆排序 
排序的平均时间复杂度为O(n•n)的算法是：冒泡排序、插入排序、选择排序 
排序过程中的比较次数与排序方法无关的是：选择排序、归并排序 
如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，最快的算法是：堆排序 
在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法：插入排序