java list的排序算法_JAVA排序汇总（List、数组排序、几种常用排序算法）

List排序

1、使用Collections的sort(List list)方法对List集合进行从小到大排序

/*** 使用Collections的sort(List list)方法对List集合进行从小到大排序*/@Testpublic voidlistDefaultSort() {

List list = new ArrayList();

list.add(1);

list.add(3);

list.add(2);

System.out.println(list);

System.out.println("------------------");

Collections.sort(list);//按从小到大排序，只能对基本数据类型的包装对象

System.out.println(list);

}

View Code

执行结果：

[1, 3, 2]------------------[1, 2, 3]

View Code

2、使用Collections的sort(List list, Comparator super T> c)方法对List集合进行自定义排序

/*** 使用Collections的sort(List list, Comparator super T> c)方法对List集合进行自定义排序*/@Testpublic voidlistCustomSort() {

List list = new ArrayList();

Person p1= new Person("1", "p1" , 12);

Person p2= new Person("2", "p2" , 9);

Person p3= new Person("3", "p3" , 13);

Person p4= new Person("4", "p4" , 9);

list.add(p1);

list.add(p2);

list.add(p3);

list.add(p4);

System.out.println(list);

System.out.println("------------------");

Collections.sort(list,new Comparator() {//按年龄从大到小排序

@Overridepublic intcompare(Person p1, Person p2) {return p1.getAge() == p2.getAge() ? 0 : (p1.getAge() < p2.getAge() ? 1 : -1);

}

});

System.out.println(list);

}

View Code

classPerson {privateString id;privateString name;private intage;public Person(String id, String name, intage) {super();this.id =id;this.name =name;this.age =age;

}publicString getId() {returnid;

}public voidsetId(String id) {this.id =id;

}publicString getName() {returnname;

}public voidsetName(String name) {this.name =name;

}public intgetAge() {returnage;

}public void setAge(intage) {this.age =age;

}

@OverridepublicString toString() {return "\n Person [id=" + id + ", name=" + name + ", age=" + age + "]";

}

}

View Code

执行结果：

[

Person [id=1, name=p1, age=12],

Person [id=2, name=p2, age=9],

Person [id=3, name=p3, age=13],

Person [id=4, name=p4, age=9]]------------------[

Person [id=3, name=p3, age=13],

Person [id=1, name=p1, age=12],

Person [id=2, name=p2, age=9],

Person [id=4, name=p4, age=9]]

View Code

数组排序

1、使用Arrays.sort(int[] a)方法对数组按从小到大排序

/*** 使用Arrays.sort(int[] a)方法对数组按从小到大排序*/@Testpublic voidarrayDefaultSort() {int[] array = {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

System.out.println("");

System.out.println("---------------------");

Arrays.sort(array);//按从小到大排序，只能对基本数据类型以及其封装对象

for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

}

View Code

执行结果：

3 4 6 1 8 2 1 5 9 0

---------------------

0 1 1 2 3 4 5 6 8 9

View Code

2、使用Arrays.sort(int[] a, int fromIndex, int toIndex)部分从小到大排序

/*** 使用Arrays.sort(int[] a, int fromIndex, int toIndex)部分从小到大排序

* fromIndex 要排序的第一位索引(包括，从这开始)

* toIndex 要排序的最后一个索引(不包括在内，在这结束)*/@Testpublic voidarrayPartSort() {

Integer[] array= {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

System.out.println("");

System.out.println("---------------------");

Arrays.sort(array,3, 6); //对下标为3至6(不包括6)按从小到大排序，只能对基本数据类型以及其封装对象

for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

}

View Code

执行结果：

3 4 6 1 8 2 1 5 9 0

---------------------

3 4 6 1 2 8 1 5 9 0

View Code

3、使用Arrays.sort(T[] a, Comparator super T> c)自定义排序

/*** 使用Arrays.sort(T[] a, Comparator super T> c)自定义排序*/@Testpublic voidarrayCustomSort() {

Integer[] array= {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};for(Integer i : array) {

System.out.print(i);

System.out.print(" ");

}

System.out.println("");

System.out.println("---------------------");

Arrays.sort(array,new Comparator() {//从大到小排序

@Overridepublic intcompare(Integer i1, Integer i2) {return i1 == i2 ? 0 : (i1 < i2 ? 1 : -1);

}

});for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

}

View Code

执行结果：

3 4 6 1 8 2 1 5 9 0

---------------------

9 8 6 5 4 3 2 1 1 0

View Code

常见排序算法

1、冒泡排序

/*** 冒泡排序(按从小到大排序)

* 最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)*/@Testpublic voidbubbleSort() {int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0};for (int i = 0; i < array.length; i++) {for (int j = 0; j < array.length - 1 - i; j++) {if (array[j + 1]

array[j+ 1] =array[j];

array[j]=temp;

}

}

}for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

}

View Code

2、选择排序

/*** 选择排序(按从小到大排序)

* 最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)*/@Testpublic voidselectionSort() {int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0};for (int i = 0; i < array.length; i++) {int minIndex =i;for (int j = i; j < array.length; j++) {if (array[j]

minIndex=j;

}int temp =array[minIndex];

array[minIndex]=array[i];

array[i]=temp;

}for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

}

View Code

3、插入排序

/*** 插入排序(按从小到大排序)

* 最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)*/@Testpublic voidinsertionSort() {int[] array = { 3, 4, 6, 1, 8, 2, 1, 5, 9, 0};intcurrent;for (int i = 0; i < array.length - 1; i++) {

current= array[i + 1];int preIndex =i;while (preIndex >= 0 && current

array[preIndex+ 1] =array[preIndex];

preIndex--;

}

array[preIndex+ 1] =current;

}for (inti : array) {

System.out.print(i);

System.out.print(" ");

}

}

View Code

4、希尔排序

/*** 从大到小

*@paramarray*/

public static void shellSort1(int[] array) {int number = array.length/2;inti,j,temp;while (number >= 1){for (i = number; i < array.length; i++) {

temp=array[i];

j= i -number;while (j >= 0 && array[j]

array[j+ number] =array[j];

j= j -number;

}

array[j+ number] =temp;

}

number= number/2;

}

}

View Code

5、归并排序

/*** 从小到大排序

*@paramarr*/

public static void sort(int[]array){int []temp = new int[array.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间

sort(array,0,array.length-1,temp);

}private static void sort(int[] array,int left,int right,int[]temp){if(left

sort(array,left,mid,temp);//左边归并排序，使得左子序列有序

sort(array,mid+1,right,temp);//右边归并排序，使得右子序列有序

merge(array,left,mid,right,temp);//将两个有序子数组合并操作

}

}private static void merge(int[] arr,int left,int mid,int right,int[] temp){int i = left;//左序列指针

int j = mid + 1;//右序列指针

int t = 0;//临时数组指针

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

temp[t++] = arr[i++];

}else{

temp[t++] = arr[j++];

}

}while(i <= mid){//将左边剩余元素填充进temp中

temp[t++] = arr[i++];

}while(j <= right){//将右序列剩余元素填充进temp中

temp[t++] = arr[j++];

}

t= 0;//将temp中的元素全部拷贝到原数组中

while(left <=right){

arr[left++] = temp[t++];

}

}

View Code

6、快速排序

public static voidmain(String[] args) {int[] array = new int[]{2,3,5,6,9,1,0,3,4,6};

quickSort(array);for (int i=0;i

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

}

}/*** 快速排序，使得整数数组 arr 有序*/

public static void quickSort(int[] array) {if (array == null || array.length < 2) {return;

}

quickSort(array,0, array.length - 1);

}/*** 快速排序，使得整数数组 arr 的 [L, R] 部分有序*/

public static void quickSort(int[] arr, int L, intR) {if(L

swap(arr, new Random().nextInt(R - L + 1) +L, R);int[] p =partition(arr, L, R);

quickSort(arr, L, p[0] - 1);

quickSort(arr, p[1] + 1, R);

}

}/*** 分区的过程，整数数组 arr 的[L, R]部分上，使得：

* 大于 arr[R] 的元素位于[L, R]部分的右边，但这部分数据不一定有序

* 小于 arr[R] 的元素位于[L, R]部分的左边，但这部分数据不一定有序

* 等于 arr[R] 的元素位于[L, R]部分的中间

* 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组*/

public static int[] partition(int[] arr, int L, intR) {int basic =arr[R];int less = L - 1;int more = R + 1;while(L

swap(arr,++less, L++);

}else if (arr[L] >basic) {

swap(arr,--more, L);

}else{

L++;

}

}return new int[] { less + 1, more - 1};

}/** 交换数组 arr 中下标为 i 和下标为 j 位置的元素*/

public static void swap(int[] arr, int i, intj) {int temp =arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

View Code

7、堆排序

8、计数排序

9、桶排序

10、基数排序

递归

1、递归算法计算n!

/*** 递归算法*/@Testpublic voidrecursion() {

System.out.println(factorial(2));

}/*** 递归算法计算阶乘n!

*

*@paramn

*@return

*/

public staticInteger factorial(Integer n) {if (n < 0)return 0;if (n == 1)return 1;return n * factorial(n - 1);

}

View Code

2、递归计算1*2+2*3+3*4+...+n*(n+1)

/*** 递归算法*/@Testpublic voidrecursion() {

System.out.println(productSum(4));

}/*** 递归算法计算1*2+2*3+3*4+...+n*(n+1)

*@paramn

*@return

*/

public staticInteger productSum(Integer n) {if (n <= 0)return 0;if (n == 1)return 2;int result = productSum(n - 1) + n * (n + 1);returnresult;

}

View Code