Java四种数组排序
001package algorithm.sort;
002
003
import java.util.Random;
004
005
/**
006
* <a href="http://my.oschina.net/arthor" class="referer" target="_blank">@author</a> szy
007
* 2012-7-24
008
*/
009
public class Sort {
010
/**
011
* 选择排序法
012
*
013
* 基本思路:将要排序的数组分成两部分,
014
* 一部分是从小到大已经排好序的,一部分是无序的,
015
* 从无序的部队取出最小的数值,放到已经排好序的部分的最后
016
*
017
* @param arr
018
* <a href="http://my.oschina.net/u/556800" class="referer" target="_blank">@return</a>
019
*/
020
public int[] choiceSort(int[] arr){
021
int t,i=0,j;
022
int len = arr.length;
023
for(;i<len;i++){
024
int m = i;
025
for(j=i+1;j<len;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
* <a href="http://my.oschina.net/u/556800" class="referer" target="_blank">@return</a>
052
*/
053
public int[] bubblingSort(int[] arr){
054
int t,i=0,j=0;
055
int len = arr.length;
056
for(;i<len;i++){
057
//循环比较相邻两个元素大小
058
for(;j<len-i-1;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
* <a href="http://my.oschina.net/u/556800" class="referer" target="_blank">@return</a>
080
*/
081
public int[] insertSort(int[] arr){
082
//将第一个元素看做一部分,第二个元素看做另一部分
083
//从第二部分中依次取元素插入到第一部分中
084
int i=1,j;
085
int len = arr.length;
086
for(;i<len;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
}
0
补充：软件开发 , Java ,
