[数据结构] 动图演示 代码实现八大排序（插入、希尔、选择、堆、冒泡、快速、归并、基数/桶）

2019-04-18 18:22:04

• 

• giturtle

  

  码龄3年

关注

排序

• 1. 插入排序

• 2. 希尔排序

• 3. 选择排序

• 4. 堆排序

• 5. 冒泡排序

• 6. 快速排序

• 1）Hover法

• 2）挖坑法

• 3）前后下标法

• partiton三种方法：

• [★] 快排的非递归实现

• 7. 归并排序

• 8. 基数排序

---

#pragma once#include <stdio.h>/*需要经常用到的 2 个函数，封装成为接口直接调用*///1. 交换函数void Swap(int array[], int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}//2. 打印函数void PrintArray(int array[], int size) {for (int i = 0; i < size; i ) {printf('%d ', array[i]);}printf('\n');}

• 1

• 2

• 3

• 4

• 5

• 6

• 7

• 8

• 9

• 10

• 11

• 12

• 13

• 14

• 15

• 16

• 17

• 18

• 19

• 20

• 1

• 2

• 3

• 4

• 5

• 6

• 7

• 8

• 9

• 10

• 11

• 12

• 13

• 14

• 15

• 16

• 17

• 18

• 19

• 20

时间、空间复杂度、稳定性一览

排序方法	时间复杂度(最坏)	时间复杂度(平均)	时间复杂度(最好)	空间复杂度	稳定性
插入	O（n^2）	O（n^2）	O（n）	O（1）	稳定
希尔	O（n^2）	O（n^1.3~1.4）	O（n）	O（1）	不稳定
选择	O（n^2）	O（n^2）	O（n^2）	O（1）	不稳定
堆	O(n*log(n))	O(n*log(n))	O(n*log(n))	O（1）	不稳定
冒泡	O（n^2）	O（n^2）	O（n）	O（1）	稳定
快速	O（n^2）	O(n*log(n))	O(n*log(n))	最好O(logN)平均O(logN)最坏O(N)	不稳定
归并	O(n*log(n))	O(n*log(n))	O(n*log(n))	O（N）	稳定

1. 插入排序

动图演示

代码实现

/*时间复杂度：最快：O(n)已经有序平均：O(n^2)最慢：O(n^2)逆序【数据越有序，速度越快】空间复杂度：O(1)稳定性：稳定*//*标准版*/void InsertSort(int array[], int size) {for (int i = 0; i < size; i  ) {int key = array[i];int j;// [i - 1, 0]for (j = i - 1; j >= 0; j--) {if (array[j] <= key) {break;}array[j   1] = array[j];}array[j   1] = key;}}/*讲解版*/void InsertSort2(int array[], int size) {for (int i = 0; i < size; i  ) {// array[0, i - 1] 部分是有序的// 要处理的这个数是 array[i]// array[i   1, size - 1] 部分是无序的// 我们需要在有序部分 [0, i - 1] 给 array[i] 找到合适的位置int pos = i;for (int j = 0; j <= i - 1; j  ) {// array[j] 比 array[i] 小，说明我们还没找到合适的位置// array[j] 和 array[i] 相等，为了保证稳定性，我们继续前进if (array[j] > array[i]) {pos = j;break;}}// pos 就是应该放 array[i] 的位置// 类似顺序表的插入，把 array[i] 插入到 array[0, i - 1] 所在的顺序表的 pos 下标if (pos != i) {int key = array[i];// 避免数据被覆盖，我们倒着搬数据// k 代表的是 数据应该被放到的空间的下标for (int k = i; k > pos; k--) {array[k] = array[k - 1];}array[pos] = key;}}}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960

2. 希尔排序

动图演示

代码实现

/*希尔排序 -- 插入排序进化版时间复杂度:最好: O(n)平均：O(n^1.3-1.4)最坏: O(n^2)空间复杂度:O(1)稳定性：不稳定*/void InsertSortWithGap(int array[], int size, int gap) {for (int i = 0; i < size; i ) {int key = array[i];int j;for (j = i - gap; j >= 0; j -= gap) {if (array[j] <= key) {break;}array[j gap] = array[j];}array[j gap] = key;}}void ShellSort(int array[], int size) {int gap = size;while (1) {gap = gap / 3 1;// gap = gap / 2;InsertSortWithGap(array, size, gap);if (gap == 1) {return;}}}

• 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

• 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

3. 选择排序

动图演示

代码实现

/*【直接选择】时间复杂度： O(n^2)数据不敏感空间复杂度: O(1)稳定性：不稳定*//*标准版*/void SelectSort(int array[], int size) {for (int i = 0; i < size; i  ) {int maxIdx = 0;for (int j = 0; j < size - i; j  ) {if (array[j] > array[maxIdx]) {maxIdx = j;}}Swap(array, maxIdx, size - 1 - i);}}/*讲解版*/void SelectSort2(int array[], int size) {for (int i = 0; i < size; i  ) {int record = 0;// 假设最大的数放在 array[0]// [size - i, size - 1] 有序的// [0, size - 1 - i]无序的// 在无序的部分，找到最大数的下标for (int j = 0; j <= size - 1 - i; j  ) {if (array[j] > array[record]) {record = j;}}// 整个无序部分都找完了，已经确定最大的// 把最大的数和无序部分的最后一个数进行交换Swap(array, record, size - 1 - i);}}123456789101112131415161718192021222324252627282930313233343536373839404142123456789101112131415161718192021222324252627282930313233343536373839404142

4. 堆排序

动图演示

代码实现

/*堆排序：时间复杂度：O(n * log(n))不敏感空间复杂度O(1)稳定性：不稳定*/void Heapify(int array[], int size, int rIdx) {while (1) {int leftIdx = 2 * rIdx 1;int rightIdx = 2 * rIdx 2;if (leftIdx >= size) {return;}int maxIdx;if (rightIdx >= size) {maxIdx = leftIdx;}else if (array[leftIdx] <= array[rightIdx]) {maxIdx = leftIdx;}else {maxIdx = rightIdx;}if (array[maxIdx] >= array[rIdx]) {return;}Swap(array, maxIdx, rIdx);rIdx = maxIdx;}}void CreateHeap(int array[], int size) {for (int i = (size - 1 - 1) / 2; i >= 0; i--) {Heapify(array, size, i);}}void HeapSort(int array[], int size) {CreateHeap(array, size);for (int i = 0; i < size; i ) {Swap(array, 0, size - 1 - i);Heapify(array, size - 1 - i, 0);}}

• 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

• 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

5. 冒泡排序

动图演示

代码实现

/*时间复杂度：最好：O(n)平均 O(n^2)最坏 O(n^2)空间复杂度：O(1)稳定性：稳定*//*标准版*/void BubbleSort(int array[], int size) {for (int i = 0; i < size; i  ) {int isSorted = 1;for (int j = 0; j < size - 1 - i; j  ) {if (array[j] > array[j   1]) {Swap(array, j, j   1);isSorted = 0;//标记}}//优化逻辑：如果一次交换都没有发生，则说明已经有序if (isSorted == 1) {break;}}}/*讲解版*/void BubbleSort2(int array[], int size) {for (int i = 0; i < size; i  ) {int isSorted = 1;// 每次冒泡，把一个最大的数挤到无序部分的最后去// 有序部分 [size - i, size - 1]// 无序部分 [0, size - 1 - i]// 遍历整个无序区间，挨个挤for (int j = 0; j < size - 1 - i; j  ) {if (array[j] > array[j   1]) {Swap(array, j, j   1);isSorted = 0;}}// 如果遍历整个无序区间期间，一次交换都没发生，说明// 其实无序区间是有序的if (isSorted == 1) {return;}}}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849501234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

6. 快速排序

动图演示

代码实现

/*时间复杂度：最好 O(n * log(n))平均 O(n * log(n))最坏 O(n^2)空间复杂度：最好 O(log(n))平均 O(log(n))最坏 O(n)稳定性：不稳定*/// 需要排序的区间是 [low, high]void __QuickSort(int array[], int low, int high) {// 直到// 区间长度为 0if (low > high) {return;}// 或者区间长度为 1，表示区间内的数已经有序if (low == high) {return;}// 1. 找基准值，选最左边，基准值的下标是 low// 2. 遍历整个区间，把小的放左，大的放右，返回基准值所在下标int pivotIdx = Partition_3(array, low, high);// 3. 区间被分成三部分// [low, pivotIdx - 1] 小// [pivotIdx, pivotIdx] 有序// [pivotIdx 1, high] 大// 分治算法，分别处理所有两个小区间__QuickSort(array, low, pivotIdx - 1);__QuickSort(array, pivotIdx 1, high);}void QuickSort(int array[], int size) {__QuickSort(array, 0, size - 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

• 26

• 27

• 28

• 29

• 30

• 31

• 32

• 33

• 34

• 35

• 36

• 37

• 38

• 39

• 40

• 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

partiton三种方法：

1）Hover法

// Hover 法// 对数组中 [low, high] 的区间做分组// 基准值是 array[low]int Partition_1(int array[], int low, int high) {int begin = low;// 从基准值位置开始，而不是 low   1int end = high;int pivot = array[low];// (begin, end) 的区间是没有被比较过的数据while (begin < end) {// 重点: 如果基准值在左边，需要从右边开始走while (begin < end && array[end] >= pivot) {end--;}// array[end] 比基准值小了while (begin < end && array[begin] <= pivot) {begin  ;}// array[begin] 比基准值大了// 交换 begin 和 end 下标处的数据Swap(array, begin, end);}// low 基准值// [low   1, begin] 比基准值小// [begin   1, high] 比基准值大// 把基准值和比它小的最后一个数交换Swap(array, low, begin);return begin;}1234567891011121314151617181920212223242526272829303132333412345678910111213141516171819202122232425262728293031323334

2）挖坑法

// 挖坑 法// 对数组中 [low, high] 的区间做分组// 基准值是 array[low]int Partition_2(int array[], int low, int high) {int begin = low;// 从基准值位置开始，而不是 low 1int end = high;int pivot = array[low];// begin 是坑的下标// (begin, end) 的区间是没有被比较过的数据while (begin < end) {// 重点: 如果基准值在左边，需要从右边开始走while (begin < end && array[end] >= pivot) {end--;}// array[end] 比基准值小了// 坑的下标是 beginarray[begin] = array[end];// end 是坑的下标while (begin < end && array[begin] <= pivot) {begin ;}// array[begin] 比基准值大了// 坑的下标是 endarray[end] = array[begin];// begin 变成坑的下标}// low 基准值// [low 1, begin] 比基准值小// [begin 1, high] 比基准值大// 把基准值和比它小的最后一个数交换array[begin] = pivot;return begin;}

• 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

• 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

3）前后下标法

// 前后指针（下标）法// 对数组中 [low, high] 的区间做分组// 基准值是 array[low]int Partition_3(int array[], int low, int high) {int d = low   1;int i = low   1;int pivot = array[low];while (i <= high) {if (array[i] < pivot) {Swap(array, d, i);d  ;}i  ;}Swap(array, d - 1, low);return d - 1;}12345678910111213141516171819201234567891011121314151617181920

[★] 快排的非递归实现

#include <stack>//C 版void QuickSortNoR(int array[], int size) {std::stack<int>stack;stack.push(0);// lowstack.push(size - 1);// highwhile (!stack.empty()) {int high = stack.top();stack.pop();int low = stack.top();stack.pop();if (low >= high) {continue;}int pivotIdx = Partition_2(array, low, high);// [low, pivotIdx - 1]stack.push(low);stack.push(pivotIdx - 1);// [pivotIdx 1, high]stack.push(pivotIdx 1);stack.push(high);}}

• 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

• 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

7. 归并排序

动图演示

代码实现

/*时间复杂度：O(n * log(n))空间复杂度：O(n)稳定性：稳定归并排序是 外部排序 的【首选】*/void Merge(int array[], int left, int mid, int right, int extra[]) {int i = left;// 左边区间的下标int j = mid;// 右边区间的下标int k = left;// extra 的下标while (i < mid && j < right) {if (array[i] <= array[j]) {extra[k  ] = array[i  ];}else {extra[k  ] = array[j  ];}}while (i < mid) {extra[k  ] = array[i  ];}while (j < right) {extra[k  ] = array[j  ];}// 把 extra 的数据移回来for (int x = left; x < right; x  ) {array[x] = extra[x];}}// [left, right)void __MergeSort(int array[], int left, int right, int extra[]) {// 直到// size == 1[3, 4)if (right == left   1) {return;}// size == 0if (right <= left) {return;}// 1. 把数组平均分成两部分int mid = left   (right - left) / 2;// [left, mid)// [mid, right)// 2. 分治算法，排序左右两部分__MergeSort(array, left, mid, extra);__MergeSort(array, mid, right, extra);// 3. 合并两个有序数组// [left, mid)[mid, right)Merge(array, left, mid, right, extra);}void MergeSort(int array[], int size) {int *extra = (int *)malloc(sizeof(int)* size);__MergeSort(array, 0, size, extra);free(extra);}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666712345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667

8. 基数排序

/*时间复杂度：O(n * log(n))空间复杂度：时间复杂度：最好 O(d(n rd))平均 O(d(n r))最坏 O(d(n r))空间复杂度：O(n rd)稳定性：稳定【r】：关键字的基数【d】：关键字的长度【n】：关键字的个数*/void RadixSort(int arr[],int size){ int n; for(int i = 1;i <= 100;i *= 10){ int tmp[20][10]={0}; //20行，10列，数组每一列代表0~9位数，20行表示存放的个数上限 for(int j = 0;j < size;j ){ n = (data[j] / i) % 10; tmp[j][n] = data[j]; } int k = 0; for(int p = 0;p < 10;p ) for(int q = 0;q < size;q ){ if(tmp[q][p] != 0) data[k ] = tmp[q][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

• 31

• 32

• 33

• 34

• 35

• 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

测试代码

void Test() {int array[] = { 3, 9, 1, 4, 7, 5, 2, 8, 0, 10, 9 };int size = sizeof(array) / sizeof(int);PrintArray(array, size);xxx_Sort(array, size);PrintArray(array, size);}1234567812345678

【经典数据结构】B树与B 树（动图看转载）

本文转载自：http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查... 浏览器打开

几张动态图清晰展示常用数据结构及其设计原理

最近在整理数据结构方面的知识，系统化看了下Java中常用数据结构，突发奇想用动画来绘制数据流转过程。主要基于jdk8，可能会有些特性与jdk7之前不相同，例如LinkedList LinkedHashMap中的双向列表不再是回环的。HashMap中的单链表是尾插，而不是头插入等等，后文不再赘叙这些差异，本文目录结构如下：1、LinkedList       LinkedList经典..