算法-排序算法

Posted on | In

剑指offer 第二章-面试需要的基础知识

冒泡排序

遍历数组，将最大的移到最后。逐渐缩小数组范围。

具体步骤： 1. 第一个 for 循环 P=N-1：将最大的数放到最后面 第一趟冒泡，从第一个数开始逐个向后比较，将最大的数向后移动。 2. 第二个 for 循环 P=N-2：将次大的书放到倒数第二个位置上 第二趟冒泡，从第一个数开始逐个向后比较，比较到第二个位置为止

复杂度分析： 最好情况,数组本身是顺序的，那么外循环只需要执行一次就会发现 flag 标识没变 T=O(N), 最差情况，数组本身是倒序的，那么外循环会执行 N-1 次，总的计算量是 (N-1 + N-2 +...+ 1), 则时间复杂度是 T=O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Bubble_sort(int num[], int N)
{
    for ( int P=N-1; P>0; P--)
    {
        int flag = 0;
        for (int i=0; i<P; i++)
        {
            if(num[i] > num[i+1])
            {
                int temp = num[i];
                num[i] = num[i+1];
                num[i+1] = temp;
                flag = 1;
            }
        }
        if (flag == 0) break; // 如果flag 没有发生变化，证明上一次的遍历没有发生交换，说明剩余的数组已经排序好了，就不需要缩小数组范围，继续比较了。
    }
}

插入排序

插入排序是增加增大比较范围。

从数组中先取一个数;
再取第二个数，与前面的进行比较，如果比前面的小，则交换位置。
再取第三个数，与前面的进行比较，直到找到比它大的数，插入。
依次循环。。

最好情况，本身就是个正序，外循环还是会执行完 N-1 次，但是内循环对应的只需要只执行一次，就会发现增加的数位置正确。所以总的复杂度还是 O(N) 最差情况，本身是个倒序的, 外循环会执行 N-1次， 内循环对应次数，所以总的是 O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InsertOrder(int num[], int N)
{
    for(int i=1; i<N; i++)
    {
        for(int j=i; j>0; j--)
        {
            int flag = 0;
            if (num[j] < num[j-1])
            {
                int temp = num[j];
                num[j] = num[j-1];
                num[j-1] = temp;
                flag = 1;
            }

            if(flag == 0) break;   // 这里的 flag 是放在第二个循环里面的，因为找到了位置，就停下来了，后面的排好序的肯定比他大，就不用比较了
        }
    }
}

对比冒泡排序和插入排序

  • 冒泡排序是从数组末尾到头逐渐有序，插入排序是从头到尾逐渐有序。
  • flag的位置不同。冒泡排序的外循环不一定能执行完，但内循环都会执行对应的次数。插入排序外循环一定会执行完，但内循环不一定。

堆排序

通过选择排序引入堆排序
选择排序：遍历选择最小的元素，放入数组里面。然后在无序序列里面再遍历选择最小元素，循环。。。可见时间复杂度最坏情况：O(N2)


上图可以看出 for 循环要执行 N 次，总的复杂度取决于寻找最小元。看到最小元，自然想到最小堆。最小堆的根节点就是最小值。

堆排序算法1：

针对选择排序的改进，怎么样找到最小元？可以将原序列调整成最小堆(时间复杂度是线性的 O(N))，然后依次弹出根结点 O(NlogN)。再将弹出的序列复制到原序列里面 O(N)。可见时间复杂度为：T(N)=O(N)+O(Nlog(N))+O(N)=O(Nlog(N)) 但是原数组占有O(N)内存，调整成最小堆后弹出的序列存储也需要O(N)内存，因此，空间复杂度上需要额外的O(N)

堆排序算法2

先调整成最大堆O(N),再将根结点与最后一个元素交换位置O(logN)，然后再将前N-1个元素调整成最大堆，依次循环。。最后直接就是排序的结果，而不用重新占用内存空间。时间复杂度：O(N)+O(Nlog(N))…但陈姥姥给的是下面这样…so？

代码实现

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
//堆排序
/*因为堆排序是完全二叉树，用数组表示的，所以可以把原始序列看成树，然后进行调整*/
void HeapSort(int num[], int N) {
	/*build max heap*/
	int i,temp;
	for (i = 1; i < N; i++) {   //从数组下标为1的元素开始，类似于最大堆的插入一样，依次与父节点比较
		temp = num[i];// 因为i一直在变化，因此把他保存
		for (; num[i] > num[(i-1)/2]; i = (i - 1) / 2)
			num[i] = num[(i - 1) / 2];  //把比num[i]小的父节点往下一层移
		num[i] = temp;
	}
	/*delete max and swaps the max with the last one of the unoder sequence*/
	int j,k, tempp;
	for (j = N - 1; j > 0; j--) {
		tempp = num[0];
		num[0] = num[j];
		num[j] = tempp;
		for (k = 1; k < j; k++) {   //从数组下标为1的元素开始，类似于最大堆的插入一样，依次与父节点比较
			tempp = num[k];// 因为i一直在变化，因此把他保存
			for (; num[k] > num[(k - 1) / 2]; k = (k - 1) / 2)
				num[k] = num[(k - 1) / 2];  //把比num[i]小的父节点往下一层移
			num[k] = tempp;
		}
	}
}

快速排序

算法概述：分而治之（递归）
快速排序的细节很重要：
- 选主元：中分显然是最好的
- 怎么分成两个独立子集

最好情况： 每次选择的主元位置正好在中分位置， T(N) = O(NlogN)

选主元

随机选主元：随机函数也很浪费时间。。
选头中尾三个数的中位数

这里主元是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 主元所在的位置
int Center = (Left + Right) / 2;
// 比较 左中右三个数，并排序
if (A[Left] > A[Center])
  Swap (&A[Left], &A[Center]);
if (A[Left] > A[Right])
  Swap (&A[Left], &A[Right]);
if (A[Center] > A[Right])
  Swap (&A[Center], &A[Right]);

// 再耍个小聪明， 将 pivot 藏在最右边
Swap (&A[Center], &A[Right-1]);

// 只需考虑 A[Left+1]...A[Right-2]
return A[Right-1];  // 返回 pivot

子集划分

调用过上面的 Median3 函数之后得到的数组是： {8, 1, 4, 9, 0, 3, 5, 2, 7, 6}， Left 和 Right 不用考虑了，已经在正确的子集了，pivot 也放在了剩下部分的最右边。


这里 i j 是两个指针，其实就是元素下标。当两边指针i遇到比pivot大式，停止。转去考虑右边的指针j，当j遇到小于pivot的数时也停止。此时两边都发出红色警告（也就是左边大于pivot， 右边小于pivot），则交换两边的数。

递归：对左子集重复上面的操作，对右子集重复上面的操作。

快速排序为什么快？
因为选择了一个主元，然后划分完子集后，这个主元就处于它最终所在的位置上。
比如插入排序的数的位置都是临时的，插入排序新增加一个数，从后往前逐渐对比，发现比前面的小的话，相当于把前面的数都往后挪。

如果有两元素正好等于 pivot 怎么办？
停下来交换，这样的目的是让 pivot 最终的位置更靠近数组中分的位置。之前做过时间复杂度分析时，我们知道这样的时间复杂度是最小的。

小规模数据的处理

当递归的数据规模较小时，则停止递归，使用插入排序。

代码实现

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
76
77
78
79
80
81
82
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>

void InsertSort(int num[], int N) {
  int i, j, temp;
  for (i = 1; i < N; i++) {
    for (j = i; j > 0; j--) {
      int flag = 0;
      if (num[j] < num[j - 1]) {
        temp = num[j];
        num[j] = num[j - 1];
        num[j - 1] = temp;
        flag = 1;
      }
      if (flag == 0) break;
    }

  }
}

/*选主元*/
void swap(int num[],int m, int n) {
  int temp;
  temp = num[m];
  num[m] = num[n];
  num[n] = temp;;
}
int Median3(int num[], int left,int right) {
  int median = (left + right) / 2;
  if (num[left] > num[median])
    swap(num,left,median);
  if (num[left] > num[right])
    swap(num, left, right);
  if (num[median] > num[right])
    swap(num, right, median);
  swap(num,median,right-1);
  return num[right - 1];
}

void Quick_sort(int num[],int left,int right) {
  int Cutoff = 10;
  if (Cutoff <= right - left) {
    int pivot;
    pivot = Median3(num, left, right);
    int i = left, j = right - 1;
    for (;;) {
      while (num[i++]<pivot) {}
      while (num[j--]>pivot) {}
      if (i < j)
        swap(num,i,j);
      else break;
    }
    swap(num,i,right-1);
    Quick_sort(num, left, i - 1);
    Quick_sort(num, i + 1, right);
  }
  else
    InsertSort(num + left, right - left + 1); //num+left这种写法？？
}

void QuickSort(int num[], int N)
{
  Quick_sort(num, 0, N - 1);
}


int main() {
  int N, i, j;
  scanf_s("%d", &N);
  int *num = (int*)malloc(N * sizeof(int));
  for (i = 0; i < N; i++) {
    scanf_s("%d", &num[i]);
  }
  QuickSort(num, N);
  //int pivot = Median3(num, 0, N - 1);
  //printf("%d ", pivot);
  printf("%d", num[0]);
  for (j = 1; j < N; j++)
    printf(" %d", num[j]);

}

在此过程中出现的问题： 在快速排序的C代码出现了“段错误”Segmentation fault (core dumped) 错误代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Quick_sort(int num[],int left,int right) {
  int Cutoff = 0;
  if (Cutoff <= right - left) {
    int pivot;
    pivot = Median3(num, left, right);
    int i = left, j = right - 1;
    for (;;) {
      while (num[++i]<pivot) {}
      while (num[--j]>pivot) {}
      if (i < j)
        swap(num,i,j);
      else break;
    }
    swap(num,i,right-1);
    Quick_sort(num, left, i - 1);
    Quick_sort(num, i + 1, right);
  }
  else
    InsertSort(num + left, right - left + 1); //num+left这种写法？？
}

出现bug，在Linux系统下使用gdb进行调试： 分析出现bug原因： 快速排序，递归的最后会出现 left = right-1 = 0,此时num[]中只有一个元素num[0],因此进入while (num[++i]0就好了，当元素较少的时候采用插入排序~