排序算法
发表于|更新于
|阅读量:
以下排序依照从左到右升序排序，从左边第一个关键字开始。
1、插入排序
从左到右依次拿出一个关键字与原来已经排序好的序列进行比较，插入到合适的位置。
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
|
public static int[] sort(int[] arr, int n){
if(arr.length <= 0){
throw new RuntimeException("数组长度小于等于零不合法");
}
if(n < 0){
throw new RuntimeException("排序个数小于零不合法");
}
if(arr.length < n){
throw new RuntimeException("数组长度小于排序个数不合法");
}
for(int i = 0; i < n; i++){
for(int j = i; j > 0; j--){
if(arr[j] < arr[j-1]){
int tem = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tem;
}
}
}
return arr;
}
|
2、选择排序
在已经排序好的有序序列右边选择一个最小的关键字，与有序序列最右端的下一个元素进行交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static int[] sort(int[] arr, int n){
for (int i = 0; i < n; i++){
int min = arr[i];
int index = i;
for (int j = i; j < arr.length; j++){
if(arr[j] < min){
min = arr[j];
index = j;
}
}
int tem = arr[i];
arr[i] = arr[index];
arr[index] = tem;
}
return arr;
}
|
3、冒泡排序
选择最左边的第一个关键字，依次与其右边的全部关键字进行比较，大于右边的关键字则交换，小于右边的关键字不处理。
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
|
public static int[] sort(int[] arr, int n){
int tem;
for (int i = 0; i < n; i++ ){
int flag = 0;
for (int j = 0; j < arr.length-i-1; j++){
if(arr[j] > arr[j+1]){
tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
flag = 1;
}
}
if(flag == 0){
return arr;
}
}
return arr;
}
|
4、希尔排序
插入排序的改进版，每次取数组长度的一半向下取整作为增量，依次向右边进行插入排序。
每轮完成后，新的增量去原来增量的一半向下取整作为新的增量，依次向右边进行插入排序，直到增量为1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static int[] sort(int[] arr, int n){
int tem;
for (int gap = n/2; gap > 0; gap/=2){
for (int i = gap; i < n; i++){
tem = arr[i];
int j;
for (j = i; j >= gap && arr[j-gap] > tem; j-=gap){
arr[j] = arr[j-gap];
}
arr[j] = tem;
}
}
return arr;
}
|
5、快速排序
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
|
public static void quickSort(int[] arr, int low, int high){
int temp;
int i = low, j = high;
if(low < high){
temp = arr[low];
while (i < j){
while (j > i && arr[j] > temp) --j;
if(j > i){
arr[i] = arr[j];
++i;
}
while (i < j && arr[i] < temp) ++i;
if(i < j){
arr[j] = arr[i];
--j;
}
}
arr[i] = temp;
quickSort(arr, low, i-1);
quickSort(arr, i+1, high);
}
}
|
微信
