Java的八种排序算法和代码实现
直接插入排序
- 将一个数和第二个数排序，然后构成一个有序序列。
- 将第三个数插入进去，构成一个新的有序序列。
- 对第四个数，第五个数…直到最后一个数，重复第二步
1 | public void insertSort(int[] a){ |
希尔排序
- 将数的个数设为n，取奇数k=n/2，将下表差值为k的数分为一组，构成有序序列。
- 再取k=k/2，将下标差值为k的数分为一组，构成有序序列。
- 重复第二步，直到k=1执行简单插入排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19private static void shellSort(int[] a){
int n = a.length;
//进行分组，最开始的增量（gap）是长度的一半
for(int gap = n/2;gap > 0;gap /= 2){
//对各个分组进行插入排序
for(int i = gap;i < n;i++){
//将a[i]插入到正确的位置上
insertI(a,gap,i);
}
}
}
private static void insertI(int[] a, int gap, int i){
int insertNum = a[i];
int j;
for(j = i - gap;j >= 0 && insertNum < a[j];j-=gap){
a[j+gap] = a[j];
}
a[j + gap] = insertNum;
}简单选择排序
常用与取序列中最大最小的几个数时。 - 遍历整个序列，将最小的数放在最前面
- 遍历剩下的序列，将最小的数放在最前面
- 重复第二步，直到只剩下一个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17private static void selectSort(int[] a){
int length = a.length;
int key; //用来存储循环时遇到的最小值
int position; //记录最小值所在的位置
for(int i = 0;i < length; i++){
key = a[i];
position = i;
for(int j = i + 1;j < length;j++){
if(a[j] < key){
key = a[j];
position = j;
}
}
a[position]=a[i];
a[i] = key;
}
}堆排序
对简单选择排序的优化 - 将序列构建成大顶堆
- 将根节点与最后一个节点交换，然后断开最后一个节点
- 重复第一、二步操作，直到所有节点断开
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
44
45
46
47
48
49
50
51
52
53
54
55
56import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[] { 9, 6, 8, 7, 0, 1, 10, 4, 2 };
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
// 开始位置是最后一个非叶子节点，即最后一个节点的父节点
int start = (arr.length - 1) / 2;
// 结束位置，数组的长度减1
for (int i = start; i >= 0; i--) {
maxHeap(arr, arr.length, i);
}
//先把数组中的第0个和堆中的最后一个数交换位置，再把前面的处理为大顶堆
for (int i = arr.length - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//这里的index为0是因为后面的已经是大顶堆，只改变的第零个元素，只需要找到它的位置
maxHeap(arr, i, 0);
}
}
/**
*
* @param arr 传入的数组
* @param size 转化的规模
* @param index 找到需要调整的子树的根节点
*/
public static void maxHeap(int[] arr, int size, int index) {
// 左子节点
int leftNode = index * 2 + 1;
// 右子节点
int rightNode = 2 * index + 2;
// 和两个子节点分别对比，找出最大的节点
int max = index;
if (leftNode < size && arr[leftNode] > arr[max]) {
max = leftNode;
}
if (rightNode < size && arr[rightNode] > arr[max]) {
max = rightNode;
}
// 交换位置
if (max != index) {
int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
// 交换位置之后，可能会破坏之前排好的堆，需要重新调整
maxHeap(arr, size, max);
}
}
}冒泡排序
- 将序列中所有元素两两比较，将最大的放在最后面
- 将剩余序列中所有元素两两比较，将最大的放在最后面
- 重复第二步，直到只剩下一个数
1
2
3
4
5
6
7
8
9
10
11
12
13private static void bubbleSort(int[] a){
int length = a.length;
int temp;
for(int i = 0;i < length;i++){
for(int j = 0;j < length - 1; j++){
if(a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}快速排序
要求时间最快时 - 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
- 递归的将p左边和右边的数都按照第一步进行，直到递归结束。
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
31private static void qucikSort(int[] a, int low, int high){
if(low < high){
//寻找基准数据的正确索引
int index = getIndex(a, low, high);
//进行迭代对index之前和之后的数组进行相同的操作使得整个数组变成有序
qucikSort(a,low,index - 1);
qucikSort(a,index + 1, high);
}
}
private static int getIndex(int[] a, int low, int high) {
//基准数据
int tmp = a[low];
while(low < high){
//当队尾的元素大于或等于基准数据时，向前移动high指针
while(low < high && a[high] >= tmp){
high--;
}
//如果队尾元素小于tmp，就把它赋值给low
a[low] = a[high];
//当队首元素小于或等于tmp时，向后挪动low指针
while(low < high && a[low] <= tmp ){
low++;
}
//当队首元素大于tmp时，需要将其赋值给high
a[high] = a[low];
}
//跳出循环时low和high相等，此时的low或high就是tmp的正确索引位置
a[low] = tmp;
return low;
}
