排序算法

简介

  • 常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。
    在冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。
  • 比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。
  • 计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。
  • 非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)。
  • 非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

术语

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
  • 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
  • 内排序:所有排序操作都在内存中完成;
  • 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 时间复杂度: 一个算法执行所耗费的时间。
  • 空间复杂度:运行完一个程序所需内存的大小。
  • n: 数据规模
  • k: “桶”的个数
  • In-place: 占用常数内存,不占用额外内存
  • Out-place: 占用额外内存

冒泡排序

  • 冒泡排序的英文Bubble Sort,是一种最基础的交换排序。
  • 冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
* 冒泡排序思路
* 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
* 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
*/
public static void maopao(){
int [] array={1,4,3,2,8,5,9,10};
//临时变量 存储比价后最大的元素
int tmp=0;



for (int i = 0; i < array.length; i++) {
//有序标记,每一轮的初始是true
boolean isSorted = true;
//内部循环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换。
for (int j = 0; j < array.length-i-1; j++) {
if(array[j]>array[j+1]){
tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
isSorted=false; //还有元素交换 所以不是有序
}

}
//如果没有元素交换 说明后面回合都是有序的 无需排序
if(isSorted){
break;
}
}
System.out.println("排序后的结果:"+Arrays.toString(array));
}



/***
* 冒泡排序优化:
* 比如 数列是: 3 4 2 1 4 5 6 7 8 9
* 这个数列的特点是前半部分(3,4,2,1)无序,后半部分(5,6,7,8)升序,并且后半部分的元素已经是数列最大值。
* 所以只需要排序前半部分即可 所以要判断出数列有序元素的位置。
*/
public static void maopao2(){
int [] array={1,4,3,2,8,5,9,10};
//临时变量 存储比价后最大的元素
int tmp=0;

//记录最后一次交换的位置
int lastExchangeIndex =0;
//无序数列的边界,每次比较只需要比到这里为止
int sortBorder =array.length -1;
for (int i = 0; i < array.length; i++) {
//有序标记,每一轮的初始是true
boolean isSorted = true;
//内部循环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换。
for (int j = 0; j <sortBorder; j++) {
if(array[j]>array[j+1]){
tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
//有元素交换,所以不是有序,标记变为false
isSorted =false;
//把无序数列的边界更新为最后一次交换元素的位置
lastExchangeIndex =j;
}

}
// sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。
sortBorder =lastExchangeIndex ;
//如果没有元素交换 说明后面回合都是有序的 无需排序
if(isSorted){
break;
}
}
System.out.println("排序后的结果:"+Arrays.toString(array));
}

选择排序

  • 表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度
  • 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void selectOrder(){
int [] array={1,4,3,2,8,5,9,10};
for (int i = 0; i < array.length; i++){
//最小元素的小标 ,默认是未排序的列的起始元素
int minIndex=i;
for (int j =i; j < array.length; j++) {
if(array[j]<array[minIndex]){
minIndex=j; //找到最小的元数索引 循坏排毒 取得最小的
}
}
//内层循坏每轮结束后,取得最小元素值
int temp=array[minIndex];
//当前找到最和当前为排序列末尾小标元素值位置 互换
array[minIndex] = array[i];
//把找到最小元素,存放到未排序排序序列的起始位置
array[i] = temp;
}

System.out.println("选择排序:"+Arrays.toString(array));
}

插入排序

它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void insertionSort() {
int [] array={1,4,3,2,8,5,9,10};
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1];
int preIndex = i;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
System.out.println(Arrays.toString(array));
}
System.out.println(Arrays.toString(array));
}

参考链接 :https://www.cnblogs.com/guoyaohua/p/8600214.html

本文原创,商业转载请联系作者获得授权,非商业转载请注明出处。

评论

发送评论 编辑评论


                        

待分类分类热门文章

标签热门文章排行

☛免责声明 ☛本站使用教程
Theme Argon With Ry-Plus By 清欢
我的第16387位朋友,历经92615次回眸才与你相遇