Ignite

数据结构

2017-07-27

  1. 排序:

概念:将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

分类:

  • 内部排序和
  • 外部排序(数据量大时,需要将数据从内存调到外存)

排序的性质:

  • 稳定排序
  • 不稳定排序(某个算法规定a>b,在排序过程中始终a>b)

常用内部排序:

  • 插入排序:(按查找的方式不同)直接插入排序、折半插入排序、2路插入排序、表插入排序、希尔排序
  • 交换类排序:冒泡排序、 快速排序
  • 选择类排序:简单选择排序、堆排序
  • 归并排序
  • 分配类排序:多关键字排序、基数排序

1、 直接插入排序:

① 思想:将一个元素插入到一个有序表中。下标为 0 的位置作为检测位,从一个元素逐步扩大有序序列

② 时间复杂度:平均情况:O(n²) 最好情况:O(n) 最坏情况:O(n²)

③ 空间复杂度:S(n) = O(1)

④ 稳定性:稳定排序。
举例:100个数时无序的,先取一个数(习惯取第一个数)拿出来作为有序序列,再将剩下的99个数里取出一个数,插入到有序序列,有序序列在增大,无序序列在减小,排序完成

⑤ 程序:

1
2
3
4
5
6
7
8
9
10
11
for (i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) { // 这个加不加都可以
temp = a[i]; // 把数组0位置的元素看作有序序列,从数组一位置开始,先把temp=a[1],保留a[1],
for (j = i - 1; j >= 0 && temp < a[j]; j--) {
// 判断a[i-1]与temp的大小 如果temp<a[i-1],把a[i-1](大于temp的数后移一位)
a[j + 1] = a[j];
a[j] = temp; // 直到j减为0 把 temp的值赋值给a[0]; 这里相当于每次都将temp与左边比它大的数交换
}
// 这里也可以这样a[j+1]=temp; 与 a[j] = temp; 执行结果类似,它是把temp这个位置的值空开了
}
}

2、 折半插入排序

① 思想:因为是已经确定了前部分是有序序列,所以在查找插入位置的时候可以用折半查找的方法进行查找,提高效率。

② 时间复杂度:比较时的时间减为O(n㏒n),但是移动元素的时间耗费未变,所以总是得时间复杂度还是O(n²)。

③ 空间复杂度:S(n) = O(1)。

④ 稳定性:稳定排序。

⑤ 程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(i=1;i<a.length;i++){
if(a[i]<a[i-1]){ //没有这个判断也可以
temp=a[i]; //把a[i]的值缓存
low=0; high=i-1; //标明上界和下界
while(low<=high){ //low=high的时候停止
mid=(low+high)/2;
if(temp>a[mid]){
low=mid+1;
}else high=mid-1;
}
for(j=i;j>low;j--){ //所有大于temp的数都后移一位 (因为j>low所以a[low]取不到)
a[j]=a[j-1] ; //最后一次移位是将a[low+1]=a[low]
}
a[low]=temp; //然后把temp的值给a[low]
}
}

(了解) 2-路插入排序

① 思想:减少直接插入法的移动元素个数,分成两路子有序序列,需要N个记录的辅助空间

(了解) 表插入排序

① 思想:对静态链表做插入排序

做法:将一个记录插入到已排好序的有序表中,与直接插入不同,已修改2n次指针值代替移动记录

3、 希尔排序

① 思想:又称缩小增量排序法。把待排序序列分成若干较小的子序列,然后逐个使用直接插入排序法排序,最后再对一个较为有序的序列进行一次排序,主要是为了减少移动的次数,提高效率。这里是将增量以元素个数的一半开始。

                   38,49,65,97,76,13,27,49
                    |     |     |     |
                    0  1  2  3  4  5  6  7

② 时间复杂度: 平均情况:O(n^1.5) 最好情况:O(n) 最坏情况:O(n²)

③ 空间复杂度:O(1)

④ 稳定性:不稳定排序。{2,4,1,2},2和1一组4和2一组,进行希尔排序,第一个2和最后一个2会发生位置上的变化。

⑤ 程序:

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[] a){
int i,j,temp;
int n=a.length;
int d=n/2; //以一半分组
while(d>=1){
//直接插入排序 把每组内的元素都看成一个序列,对这个序列进行直接插入排序
for(i=d;i<a.length;i++){ //i++控制 每组要做比较
temp=a[i];
for(j=i-d;j>=0&&temp<a[j];j=j-d){
a[j+d]=a[j];
}
a[j+d]=temp;
}
d/=2;
}
for (int k : a) {
System.out.print(" "+k);
}
return 0;
}

4、 冒泡排序

① 思想:反复扫描待排序序列,在扫描的过程中顺次比较相邻的两个元素的大小,若逆序就交换位置。第一趟,从第一个数据开始,比较相邻的两个数据,(以升序为例)如果大就交换,得到一个最大数据在末尾;然后进行第二趟,只扫描前n-1个元素,得到次大的放在倒数第二位。以此类推,最后得到升序序列。如果在扫描过程中,发现没有交换,说明已经排好序列,直接终止扫描。所以最多进行n-1趟扫描。

② 时间复杂度:平均 \最坏O(n²) 最好 O(n)

③ 空间复杂度:S(n) = O(1)。

④ 稳定性:稳定排序。

⑤ 程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void Sort(int[] a){
for(int i=0;i<a.length-1;i++){ //控制每一趟的比较,因为比较一趟就有一个数不用比较了(i=0 循环完,一个数就不用考虑了,以此类推)需要比较
//比较7次,但是最后一轮,剩下的最后一个数就确定了不用比较了,所以比较6次 即<a.lenth-1 ,注意是<
for(int j=0;j<a.length-1-i;j++){ // 因为每次比较完都少一个数所以在a.length-1基础上减i
if(a[j+1]<=a[j]){
int temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
for (int k : a) {
System.out.println(k);
}
}

5、 快速排序

① 思想:

E1:对待排序序列进行划分,使前一部分的key值均小于后一部分;为此需要选定枢轴(支点)

E2:对前半子序列进行快速排序;

E3:对后半子序列进行快速排序;

思路: low --------- high

以第一个元素为基准,先从后往前看

low 左面都比它小,遇到一个比它大的数就换到后面,然后high-1

high 右面的数都不小于它,遇到一个比它小的数,就换到前面,然后low+1
② 时间复杂度:平均T(n) = O(n㏒n),最坏O(n²)。

③ 空间复杂度:S(n) = O(㏒n)。

④ 稳定性:不稳定排序。{3, 2, 2}

⑤ 程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void Sort(int a[], int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = a[i]; // 用子表的第一个记录做基准
while (i < j) { // 从表的两端交替向中间扫描
while (i < j && a[j] >= index) //控制
j--;
if (i < j)
a[i++] = a[j]; // 用比基准小的记录替换低位记录
while (i < j && a[i] < index)
i++;
if (i < j) // 用比基准大的记录替换高位记录
a[j--] = a[i];
}
a[i] = index; // 将基准数值替换回 a[i]
Sort(a, low, i - 1); // 对低子表进行递归排序
Sort(a, i + 1, hight); // 对高子表进行递归排序

}

6、 简单选择排序:
① 思想:第一趟时,从第一个记录开始,通过n – 1次关键字的比较,从n个记录中选出关键字最小的记录,并和第一个记录进行交换。第二趟从第二个记录开始,选择最小的和第二个记录交换。以此类推,直至全部排序完毕。 /选择排序与前面的简单(冒泡)排序算法思路一模一样,不同的地方在于,在寻找最小元素的时候,前者是每次都将最小元素存放到目的地,而后者则只是暂时存放一下其地址,到最后的时候才需要交换。因此,后者省略了很多的交换操作,更优。/

② 时间复杂度:最好、最坏、平均情况都是O(n²)。

③ 空间复杂度:S(n) = O(1)。

④ 稳定性:不稳定排序,{3, 3, 2}。

⑤ 程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void Sort(int[] a){
int min;
for(int i=0;i<a.length-1;i++) //假设有n个元素,需要确定的下标有0到n-1。最后一个元素无需比较
{ min=i;
for(int j=i+1;j<a.length;j++){
if(a[j]<a[min]) //使min总是指向最小的元素
min=j;
}
if(min!=i){ //min有移动过
int temp =a[i];
a[i]=a[min];
a[min]=temp;

}
}
}

7、堆排序

① 思想:把待排序记录的关键字存放在数组r[1…n]中,将r看成是一刻完全二叉树的顺序表示,每个节点表示一个记录,第一个记录r[1]作为二叉树的根,一下个记录r[2…n]依次逐层从左到右顺序排列,任意节点r[i]的左孩子是r[2i],右孩子是r[2i+1],双亲是r[i/2向下取整]。然后对这棵完全二叉树进行调整建堆。

设有一个关键字集合,按完全二叉树的顺序存储方式存放在一个一维数组中。若满足
Ki <= K2i Ki >= K2i
Ki <= K2i+1 或 Ki >= K2i+1
则称该关键字集合构成一个堆;
前者成为小顶堆,后者称为大顶堆。其中二叉树的根结点称为堆顶。
i 和 (2i和2i+1)比较
存储结构:数组
对应逻辑结构: 二叉树

② 时间复杂度:T(n) = O(n㏒n)。(平均、最好、最坏情况都是)

③ 空间复杂度:S(n) = O(1)。

④ 稳定性:不稳定排序。{5, 5, 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
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
public class HeapSort {

public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}

buildMaxHeap(array); // 建立大顶堆

for (int i = array.length - 1; i >= 1; i--) {
ArrayUtils.exchangeElements(array, 0, i); // 输出堆顶元素和堆底元素交换

maxHeap(array, i, 0);
}
}

private static void buildMaxHeap(int[] array) {
if (array == null || array.length <= 1) {
return;
}

int half = array.length / 2; // 从i=[n/2]---1反复调整堆
for (int i = half; i >= 0; i--) {
maxHeap(array, array.length, i);
}
}

private static void maxHeap(int[] array, int heapSize, int index) {
int left = index * 2 + 1; // 调整元素
int right = index * 2 + 2;

int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}

if (right < heapSize && array[right] > array[largest]) {
largest = right;
}

if (index != largest) {
ArrayUtils.exchangeElements(array, index, largest);

maxHeap(array, heapSize, largest);
}
}

public static void main(String[] args) {
int[] array = { 60, 45, 30, 14, 2, 85, 42, 30 };

System.out.println("Before heap:");
ArrayUtils.printArray(array);

heapSort(array);

System.out.println("After heap sort:");
ArrayUtils.printArray(array);
}
}

8、归并排序
① 思想:假设初始序列右n个记录,首先将这n个记录看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2向上取整 个长度为2(n为奇数时,最后一个序列的长度为1)的有序子序列。在此基础上,在对长度为2的有序子序列进行两两归并,得到若干个长度为4的有序子序列。如此重复,直至得到一个长度为n的有序序列为止。将两个或两个以上的有序表组合成一个新的有序表

② 时间复杂度:T(n) = O(n㏒n)。(平均、最坏、最好情况都是)

③ 空间复杂度:S(n) = O(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
55
56
57
58
59
60
61
public class MergeSort {
/**
* 归并排序
* 简介:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
* 时间复杂度为O(nlogn)
* 稳定排序方式
* @param nums 待排序数组
* @return 输出有序数组
*/
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2; //先分一半
if (low < high) {
// 左边
sort(nums, low, mid);
// 右边
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}

public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;

// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}

// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}

// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}

// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
// 归并排序的实现
public static void main(String[] args) {

int[] nums = {5,2,95,48,32,45,11,97,48};

MergeSort.sort(nums, 0, nums.length-1);
ArrayUtils.printArray(nums);
}
}

9、分配类排序

一、多关键字的排序

  • 高位优先法
  • 划分子序列的思想
  • 低位优先法
  • 分配再收集的思想

二、链式基数排序
① 思想:先分配,再收集,就是先按照一个次关键字收集一下,然后进行收集(第一个排序),然后再换一个关键字把新序列分配一下,然后再收集起来,又完成一次排序,这样所有关键字分配收集完后,就完成了排序。

② 时间复杂度:T(n) = O( d ( n + rd ) )。

③ 空间复杂度:S(n) = O(rd)。

④ 稳定性:稳定排序。

⑤ 程序:

10、 总结:

(1)简单排序法一般只用于n较小的情况(例如n<30)。当序列的记录“基本有序”时,直接插入排序是最佳的排序方法。如果记录中的数据较多,则应采用移动次数较少的简单选择排序法。

(2)快速排序、堆排序和归并排序的平均时间复杂度均为O(n㏒n),但实验结果表明,就平均时间性能而言,快速排序是所有排序方法中最好的。遗憾的是,快速排序在最坏情况下的时间性能为O(n²)。堆排序和归并排序的最坏时间复杂度仍为O(n㏒n),当n较大时,归并排序的时间性能优于堆排序,但它所需的辅助空间最多。

(3)可以将简单排序法与性能较好的排序方法结合使用。例如,在快速排序中,当划分子区间的长度小于某值时,可以转而调用直接插入排序法;或者先将待排序序列划分成若干子序列,分别进行直接插入排序,然后再利用归并排序法,将有序子序列合并成一个完整的有序序列。

(4)基数排序的时间复杂度可以写成O(d·n)。因此,它最适合于n值很大而关键字的位数d较小的序列。当d远小于n时,其时间复杂度接近O(n)。

(5)从排序的稳定性上来看,在所有简单排序法中,简单选择排序是不稳定的,其他各种简单排序法都是稳定的。然而,在那些时间性能较好的排序方法中,希尔排序、快速排序、堆排序都是不稳定的,只有归并排序、基数排序是稳定的。

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章