Java四种数组排序 - JAVA

001
package algorithm.sort;
002

003
import java.util.Random;
004

005
/**
006
* @author szy
007
* 2012-7-24
008
*/
009
public class Sort {
010
/**
011
* 选择排序法
012
*
013
* 基本思路:将要排序的数组分成两部分,
014
* 一部分是从小到大已经排好序的,一部分是无序的,
015
* 从无序的部队取出最小的数值,放到已经排好序的部分的最后
016
*
017
* @param arr
018
* @return
019
*/
020
public int[] choiceSort(int[] arr){
021
int t,i=0,j;
022
int len = arr.length;
023
for(;i 024
int m = i;
025
for(j=i+1;j 026
//如果j元素比m元素小,将j赋值给m
027
if(arr[j] < arr[m]){
028
m=j;
029
}
030
}
031
//交换m和i两个元素的位置
032
if(i != m){
033
t = arr[i];
034
arr[i] = arr[m];
035
arr[m]=t;
036
}
037
}
038
return arr;
039
}
040

041
/**
042
* 冒泡排序
043
*
044
* 基本思路:从数组开始扫描待排序的元素
045
* 在扫描过程中依次对相邻元素进行比较,将数值大的元素后移
046
* 每经过一趟排序后,数值最大的元素将移到末尾
047
* 此时记下该元素的位置,
048
* 下一趟排序只需要比较到些位置为止
049
* 直到所有元素都己有序排列
050
* @param arr
051
* @return
052
*/
053
public int[] bubblingSort(int[] arr){
054
int t,i=0,j=0;
055
int len = arr.length;
056
for(;i 057
//循环比较相邻两个元素大小
058
for(;j 059
//比较相邻元素大小,小的前移,大的后移
060
if(arr[j]>arr[j+1]){
061
t=arr[j];
062
arr[j]=arr[j+1];
063
arr[j+1]=t;
064
}
065

}
066
}
067
return arr;
068
}
069

070
/**
071
* 插入排序
072
*
073
* 基本思路:将要排序的数组分成两部分
074
* 每次从后面的数组部分中取出索引最小的数组元素
075
* 插入到前面数组部分的适当位置中.
076
* 通常在开始排序时,将数组的第一个元素为一组,后面的所有元素被当成另一组
077
*
078
* @param arr
079
* @return
080
*/
081
public int[] insertSort(int[] arr){
082
//将第一个元素看做一部分,第二个元素看做另一部分
083
//从第二部分中依次取元素插入到第一部分中
084
int i=1,j;
085
int len = arr.length;
086
for(;i 087
int tmp = arr[i];
088
j = i-1;
089
//依次和i前面元素比较,寻找合插入位置
090
while(tmp < arr[j]){
091
arr[j+1] = arr[j];
092
j--;
093
if(j == -1){
094
break;
095
}
096
}
097
//将插入元素插入到合适位置
098
arr[j+1] = tmp;
099
}
100
return arr;
101
}
102

103
/**
104
* 快速排序
105
*
106
* 基本思路:将一个大的数组的排序分题,分解成2个小的数组的排序
107
* 而每个小的数组排序又可以继续分解成更小的2个数组.
108
* 这样一直递归分解下去 ,直到数组的大小最大为2
109
*
110
* @param arr
111
* @param right arr.length-1
112
* @param left 0
113
* @return
114
*/
115
public int[] quickSort(int[] arr, int left, int right){
116
int t,len = arr.length;
117

118
if(left < right){
119
int s = arr[left];
120
int i = left;
121
int j = right + 1;
122
while(true){
123
//向右找大于s的数的索引
124
while(i+1 < len && arr[++i] < s );
125
//向左找小于s的数的索引
126
while(j-1 > -1 && arr[--j] > s);
127
//如果 i>=j 退出循环
128
if(i>=j)
1

Java四种数组排序(一)