0%

排序算法

排序算法

按照策略分类主要的排序算法有:插入排序、选择排序、交换排序、归并排序、分配排序

插入排序

插入排序的基本思想:每次讲一个待排序的记录,按其关键字大小插入到前面已经排好序的记录集中,直到所有排序记录全部插入成功。

直接插入排序

直接插入排序的思想

假设排序数据存放在数组A[1…n]中,则A[1]则可以看做是一个有序序列,让i从2开始,依次将A[i]插入到有序序列A[1…i-1]中,A[n]插入完毕结束

过程举例

【】中的数据为有序的

待排序的数据: 【 23】 56 2 9 17
i =2 【 23 56】 2 9 17
i=3 【 2 23 56】 9 17
i=4 【 2 9 23 56】17
i=5 【 2 9 17 23 56】
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] arrays = {23,56,2,9,17};

int i,j;
for(i = 1;i<arrays.length;i++){
// 当前值比前一个值小 需要移位
if(arrays[i] < arrays[i-1]){
int temp = arrays[i]; // 暂存
// 依次与前面的元素进行比较
for(j = i-1;j >=0 && arrays[j] > temp;j--){
arrays[j+1] = arrays[j];
}
// 找到所在位置
arrays[j+1] = temp;
}
}

System.out.println(Arrays.toString(arrays));

时间复杂度O(n^2)

希尔排序

希尔排序的思想

任取一个小于n的正数S1作为增量,将所有的元素分为S1个组,先在各组进行直接插入排序,然后取第二个增量重复上述的分组和排序,直到所取的增量等于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
int[] arrays = {130,100,56,30,23,17,9,2};

int i,j;
int gap = arrays.length /2;
int count = 1;
while (gap >= 1){
for(i = gap;i<arrays.length;i++){
// 当前值比前一个值小 需要移位
if(arrays[i] < arrays[i-1]){
int temp = arrays[i]; // 暂存
// 依次与前面的元素进行比较
for(j = i-gap;j >=0 && arrays[j] > temp;j=j-gap){
arrays[j+gap] = arrays[j];
}
// 找到所在位置
arrays[j+gap] = temp;
}
}
gap = gap / 2;
System.out.println("=======================第"+count+"次");
System.out.println(Arrays.toString(arrays));
count++;
}

System.out.println(Arrays.toString(arrays));

交换排序

交换排序的基本思想是:两两比较待排序的数据,发现两个数据的次序相反则进行交换,直到没有反序为止

冒泡排序

最多进行n-1趟排序,每趟排序自底向上扫描,一旦发现相邻的元素不符合规则,则交换,第一趟排序后,最小值在A[1],第二次排序后,最小值在A[2],依次类推,第n-1趟排序之后,所有元素按照顺序排列

过程举例

待排序的数字 10 5 2 4 3 8 6

第1次排序后
2 10 5 3 4 6 8
第2次排序后
2 3 10 5 4 6 8
第3次排序后
2 3 4 10 5 6 8
第4次排序后
2 3 4 5 10 6 8
第5次排序后
2 3 4 5 6 10 8
第6次排序后
2 3 4 5 6 8 10

代码实现
1
2
3
4
5
6
7
8
9
10
int[] arr = {10,5,2,4,3,8,6};
for(int i = 0;i< arr.length-1;i++){
for(int j = arr.length-1;j> i;j--){
if(arr[j-1] > arr[j]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}

时间复杂度为O(n^2)

快速排序

从集合中任取一个元素作为比较的基准X,将数据划分为左右两部分,A[1…i-1] <=X<=A[i+1…n],然后在分别对它们进行划分,直到全部有序为止

代码实例
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
public class QuickSort {
private static int count = 0;
static int[] data = {67,67,14,52,29,9,90,54,87,71};
public static void main(String[] args) {

quickSort(0,data.length-1);
System.out.println(Arrays.toString(data));
System.out.println(count);
}

public static void quickSort(int begin,int end){
if(begin == end || begin == (end - 1)){
return;
}
// 取第一个数作为基准
int p = data[begin];
int low = begin+1;
int hign = end;
while (low < hign){
count++;
if(data[low] > p){
if(data[hign] < p){
int temp = data[low];
data[low] = data[hign];
data[hign] = temp;
}
hign--;
} else {
low++;
}
}
// low和hign位置碰撞时,可能数据还没有和基数比较
if(data[low] > p){
data[begin] = data[low-1];
data[low-1] = p;
} else {
data[begin] = data[low];
data[low] = p;
}



System.out.println(Arrays.toString(data));
if(low-1 > begin){
System.out.println("=====低位排序======");
quickSort(begin,low-1);
}
if(end > hign+1){
System.out.println("=====高位排序======");
quickSort(hign+1,end);
}

}
}

选择排序

选择排序的基本思想是:每一趟从待排序的数据中选出最小元素,顺序放在已排好序的数据最后,直到全部数据排序完毕

直接选择排序

过程举例

待排序数据
[67, 67, 14, 52, 29, 9, 90, 54, 87, 71]
第1次排序
[9, 67, 14, 52, 29, 67, 90, 54, 87, 71]
第2次排序
[9, 14, 67, 52, 29, 67, 90, 54, 87, 71]
第3次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第4次排序
[9, 14, 29, 52, 67, 67, 90, 54, 87, 71]
第5次排序
[9, 14, 29, 52, 54, 67, 90, 67, 87, 71]
第6次排序
[9, 14, 29, 52, 54, 67, 90, 67, 87, 71]
第7次排序
[9, 14, 29, 52, 54, 67, 67, 90, 87, 71]
第8次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]
第9次排序
[9, 14, 29, 52, 54, 67, 67, 71, 87, 90]

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 0;i<data.length-1;i++){
// 记录最小值得索引位置
int min = i;
for(int j = i+1;j<data.length;j++){

if(data[min] > data[j]){
min = j;
}
}
// 找到最小位置后,进行交换
if(min != i){
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}

时间复杂度为O(n^2)

堆排序

堆排序是一种树形选择排序,分为大顶堆和小顶堆

  • 大顶堆:每个节点的值都大于等于其孩子节点的值
  • 小顶堆:每个节点的值都小于等于其孩子的值
小顶堆

根节点的元素最小是小顶堆(小于左右子节点的值)

graph TD
0((0)) --- 1((1)) --- 3((3))
1((1)) --- 4((4))
0((0)) --- 2((2))
大顶堆

根节点的元素最大是大顶堆(大于左右子节点的值)

graph TD
0((4)) --- 1((3)) --- 3((1))
1((3)) --- 4((0))
0((4)) --- 2((2))

以小顶堆为例,由于每个节点的值都小于等于其子节点的值,而且其是一个完全二叉树,也就意味着父节点和其左右子节点的索引关系为2n+1和2n+2

值得关系为arr[n] <= arr[2n+1] arr[n]<=arr[2n+2]

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
public static void main(String[] args) {
// 先找到最后一个元素的父节点索引
int index = data.length/2-1;
int length = data.length;
for(int i = index;i>=0;i--){
adjust(data,i,length);
}
// 将根节点与尾结点交换 得到新的无序数组 再次构建堆
// 依次将根节点与无序数组中的最后一个元素替换 重复操作
// 一直将堆顶元素放到堆的最后
for (int i = length-1; i >0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
adjust(data, 0, i);
}

System.out.println(Arrays.toString(data));
System.out.println(count);
}

public static void adjust(int[] data,int index,int length){
int childLeftIndex = 2*index+1;
int childRightIndex = 2*index+2;
int lowIndex = index;
count++;
// 左孩子节点大于最小索引的值
if(childLeftIndex < length && data[childLeftIndex] > data[lowIndex]){
lowIndex = childLeftIndex;
}
// 右孩子节点大于最小索引的值
if(childRightIndex < length && data[childRightIndex] > data[lowIndex]){
lowIndex = childRightIndex;
}

// 与两个子节点都比较完在进行交换,否则会导致两个子节点的值被交换
if(lowIndex != index){
int temp = data[lowIndex];
data[lowIndex] = data[index];
data[index] = temp;

// 数据交换之后可能会导致该值与其左右孩子节点的值大小不符合小顶堆,需要再次比较与其子树节点的大小关系
adjust(data,lowIndex,length);
}

}

归并排序

归并排序是将若干个已排序的数组合并成一个有序的数组

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
static int[] data = {67,67,14,52,29,9,90,54,87,71};
static int[] temp = new int[data.length];
public static void main(String[] args) {
sort(data,0,data.length-1);
System.out.println(Arrays.toString(data));
}

// 排序
public static void sort(int[] arr,int start,int end){
int middle = (start + end) / 2;
if(start < end){
// 分别排序
sort(arr,start,middle);
sort(arr,middle+1,end);
merge(arr,start,middle,end);
}
}


// 归并
public static void merge(int[] arr,int start,int middle,int end){
int i = start;
int j = middle+1;
int k = 0;
while (i <= middle && j <= end){
if(arr[i] < arr[j]){
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 此时至少有一个序列是已经全部比较完的
// 将没有比较完的一部分数据放到temp数组中
if(i <= middle){
System.arraycopy(arr,i,temp,k,middle-i+1);
} else if(j<= end){
System.arraycopy(arr,j,temp,k,end - j+1);
}
System.arraycopy(temp,0,arr,start,end - start+1);
}