Java常见排序

Java常见的排序

选择排序

Selection.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 选择排序:
* 从未排序的数组中找到最大的或者是最小的放在未排序中第一个
*/
public class Selection {
public static void main(String[] args) {
int[] array = {1,7,6,10,9,3,8,4,2,5};
for (int i = 0; i < array.length; i++) {
for (int j = i+1; j < array.length; j++) {
if(array[i] > array[j]){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}

for (int i = 0; i < array.length; i++) {
System.err.print(array[i]);
System.err.print("\t");
}
}
}

冒泡排序

Bubble.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 冒泡排序,两两比较,把最大的沉下去,把最小的浮上来
*/
public class Bubble {
public static void main(String[] args) {
//int[] array = {3,2,1};
/**
* 3,2,1
*
* 第一次排序
* 3,2,1->2,3,1
* 2,3,1->2,1,3
*
* 第二次排序
* 2,1,3->1,2,3
*/
int[] array = {1,7,6,10,9,3,8,4,2,5};
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length - (1+i); j++) {
/**
* 减多个i减少没必要的排序,因为最大的已经在上次沉到低了,这次只需要找打两两比较之中最大的沉到最后就行了
*/
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}

for (int i = 0; i < array.length; i++) {
System.err.print(array[i]);
System.err.print("\t");
}


}
}

插入排序

Insertion.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 插入排序=有序数组+无序数组
* 将无序数组的第一个放到有序数组排序
*/
public class Insertion {
public static void main(String[] args) {
int[] array = {1,7,6,10,9,3,8,4,2,5};
for (int i = 1; i < array.length; i++) {
//i=0即为第一个有序数组
//大于等于i小于array.length的为无序数组
//0到i的为有序数组

//比有序数组最后一个还要小的话,那就需要排序,否则比他大就排序(i-1)就是有序数组的最大的那个了
if(array[i]<array[i-1]){
for (int j = 0; j < i; j++) {
if(array[j]>array[i]){
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
}

for (int i = 0; i < array.length; i++) {
System.err.print(array[i]);
System.err.print("\t");
}
}
}

快速排序

QuickSort.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class QuickSort {
public static void main(String[] args) {
int[] array = {3,1,2,5,4};
quickSort(array,0,array.length-1);
for (int i = 0; i < array.length; i++) {
System.err.print(array[i]);
System.err.print("\t");
}
}

private static int partition(int[] arr, int left, int right) {
int temp = arr[left];
while (right > left) {
// 先判断基准数和后面的数依次比较
while (temp <= arr[right] && left < right) {
--right;
}
// 当基准数大于了 arr[right],则填坑
if (left < right) {
arr[left] = arr[right];
++left;
}
// 现在是 arr[right] 需要填坑了
while (temp >= arr[left] && left < right) {
++left;
}
if (left < right) {
arr[right] = arr[left];
--right;
}
}
arr[left] = temp;
return left;
}

private static void quickSort(int[] arr, int left, int right) {
if (arr == null || left >= right || arr.length <= 1)
return;
int mid = partition(arr, left, right);
quickSort(arr, left, mid);
quickSort(arr, mid + 1, right);
}
}

谢谢,爱你么么哒