Java算法——多样的排序算法（java各种排序算法）

学了很久还是发现最令人头痛的问题并不是选择学什么语言，用什么框架等，还是最基础算法，似乎永远也掌握不了，虚无缥缈，重新做个总结来加深印象！

/*

* Java数组排序(冒泡,选择,插入,希尔).

*/

public class ArraySort {

public static void main(String[] args) {

int[] arr = {2,5,6,3,1,4,8,7};

System.out.println("-----------选择排序结果------------");

slectionSort(arr);

System.out.println("\n-----------冒泡排序结果------------");

bubbleSort(arr);

System.out.println("\n-----------插入排序结果------------");

insertSort(arr);

System.out.println("\n-----------希尔排序结果------------");

shellInsert(arr);

}

public static void print(int[] arr){

for(int i=0;i<arr.length;i++){

System.out.print(" "+arr[i]);

}

}

//选择排序

public static void slectionSort(int[] arr){

for(int i=0;i<arr.length-1;i++){

int currentMin = arr[i];

int currentMinIndex= i;

for(int j=i+1;j<arr.length;j++){

if(currentMin>arr[j]){

currentMin=arr[j];

currentMinIndex = j;

}

}

if(currentMinIndex!=i){

arr[currentMinIndex] = arr[i];

arr[i] = currentMin;

}

}

print(arr);

}

//冒泡排序

public static void bubbleSort(int arr[]){

int temp = 0;

for(int i=0;i<arr.length;i++){

for(int j=i;j<arr.length;j++){

if(arr[i]>arr[j]){

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

}

print(arr);

}

//插入排序

public static void insertSort(int arr[]){

for(int i=0;i<arr.length;i++){

//寻找插入位置

int j = 0;

while(j<i&&arr[j]<=arr[i]){

j++;

}

if(j<i){

int k = i;

int temp = arr[i];

while (k > j) //挪动位置

{

arr[k] = arr[k-1];

k--;

}

arr[k] = temp; //插入

}

}

print(arr);

}

//希尔排序

/*

* 希尔排序是插入排序的一种类型，也可以用一个形象的叫法缩小增量法。基本思想就是把一个数组分为好几个数组，有点像分治法，不过这里的划分是用一个常量d来控制。

这个0<d<n,n为数组的长度。这个算法有了插入排序的速度，也可以算是一个改进算法，在插入算法中，如果有一个最小的数在数组的最后面，用插入算法就会重最后一个

位置移动到第一个，这样就会浪费很大，使用这个改进的希尔排序可以实现数据元素的大跨度的移动。也就是这个算法的优越之处。

希尔排序过程图解：

数组：45,20,80,40,26,58,66,70

d=5时 分组为：45，58

20，66

80，70

排完后为： 45，20，70，40，26，58，66，80

d=3时 分组为：45，40，66

20，26，80

70，58

40，66

26，80

排完后为：40，20，58，45，26，70，66，80

d=1时 分组为：40，20，58，45，26，70，66，80

排序后直接得到结果：

20 26 40 45 58 66 70 80

*/

public static void shellInsert(int[] List){

for(int d=5;d>0;d=d-2){

for(int c=0;c<List.length-d;c++){

for(int i=c;i<List.length;i = i+d){

for(int j=i;j>0;j=j-d){

if(j<d)

break;

if(List[j]<List[j-d]){

int t= 0;

t = List[j];

List[j] = List[j-d];

List[j-d] = t;

}

}

}

}

}

print(List);

}

}

这部分属于数据结构的知识，当初并没有很重视这门课，后悔莫及！现在恶补不知道有就没了。。。。