各种排序算法总结(共7页)

《各种排序算法总结(共7页)》由会员分享，可在线阅读，更多相关《各种排序算法总结(共7页)（7页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上各种排序算法总结排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。今天，来总结下各种排序算法。下面这个表格总结了各种排序算法的复杂度与稳定性：各种排序算法复杂度比较.png冒泡排序冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为O(n2)，其优点是实现简单，n较小时性能较好。· 算法原理相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成

2、83; c+代码实现1. void bubble_sort(int arr, int len) 2.  3.       for (int i = 0; i < len - 1; i+) 4.        5.       

3、0;   for (int j = len - 1; j >= i; j-) 6.            7.               if (arrj < arr

4、j - 1) 8.                9.                   int temp = arrj; 10.      

5、60;            arrj = arrj - 1; 11.                   arrj - 1 = temp; 12.     &

6、#160;          13.            14.        15.  选择排序· 算法原理先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 ·

7、c+代码实现1. void select_sort(int arr, int len) 2.    3.       for (int i = 0; i < len; i+) 4.        5.        

8、0;  int index = i; 6.           for (int j = i + 1; j < len; j+) 7.            8.     &

9、#160;         if (arrj < arrindex) 9.                   index = j; 10.          &#

10、160; 11.           if (index != i) 12.            13.               int temp = arri;&

11、#160;14.               arri = arrindex; 15.               arrindex = temp;  16.        

12、60;   17.        18.    插入排序· 算法原理将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n2) · c+代码实现1. void insert_sort(int arr, int len) 

13、2.    3.       for (int i = 1; i < len; i +) 4.        5.           int j = i - 1; 6. &

14、#160;         int k = arri; 7.           while (j > -1 && k < arrj ) 8.          

15、  9.               arrj + 1 = arrj; 10.               j -; 11.         

16、0;  12.           arrj + 1 = k; 13.        14.    快速排序· 算法原理快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一

17、部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 · c+代码实现1. void quick_sort(int arr, int left, int right) 2.  3.   if (left < right) 4.    5.       int

18、 i = left, j = right, target = arrleft; 6.       while (i < j) 7.        8.           while (i <

19、60;j && arrj > target) 9.               j-; 10.           if (i < j) 11.        &

20、#160;      arri+ = arrj; 12.  13.           while (i < j && arri < target) 14.            &

21、#160;  i+; 15.           if (i < j) 16.               arrj = arri; 17.        18.  

22、0;    arri = target; 19.       quick_sort(arr, left, i - 1); 20.       quick_sort(arr, i + 1, right); 21.    22.  归并排序· 算法原理归并排序具体

23、工作原理如下（假设序列共有n个元素）：o 将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素 o 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素 o 重复步骤2，直到所有元素排序完毕归并排序是稳定的排序算法，其时间复杂度为O(nlogn)，如果是使用链表的实现的话，空间复杂度可以达到O(1)，但如果是使用数组来存储数据的话，在归并的过程中，需要临时空间来存储归并好的数据，所以空间复杂度为O(n)· c+代码实现1. void merge(int arr, int 

24、temp_arr, int start_index, int mid_index, int end_index) 2.   3.      int i = start_index, j = mid_index + 1; 4.      int k = 0; 5.  &#

25、160;   while (i < mid_index + 1 && j < end_index + 1) 6.       7.          if (arri > arrj) 8.    

26、          temp_arrk+ = arrj+; 9.          else 10.              temp_arrk+ = arri+; 11.    

27、;   12.      while (i < mid_index + 1) 13.       14.          temp_arrk+ = arri+; 15.       16.   

28、;   while (j < end_index + 1) 17.          temp_arrk+ = arrj+; 18.  19.      for (i = 0, j = start_index; j < end_

29、index + 1; i +, j +) 20.          arrj = temp_arri; 21.   22.  23.  void merge_sort(int arr, int temp_arr, int start_index, int end_index) 2

30、4.   25.      if (start_index < end_index) 26.       27.          int mid_index = (start_index + end_index) / 2; 28.  

31、0;       merge_sort(arr, temp_arr, start_index, mid_index); 29.          merge_sort(arr, temp_arr, mid_index + 1, end_index); 30.       

32、0;  merge(arr, temp_arr, start_index, mid_index, end_index); 31.       32.   堆排序二叉堆二叉堆是完全二叉树或者近似完全二叉树，满足两个特性· 父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值 · 每个结点的左子树和右子树都是一个二叉堆 当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的

33、键值时为最小堆。一般二叉树简称为堆。堆的存储一般都是数组来存储堆，i结点的父结点下标就为(i 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。存储结构如图所示：堆结构.png 堆排序原理堆排序的时间复杂度为O(nlogn)· 算法原理（以最大堆为例）o 先将初始数据R1.n建成一个最大堆，此堆为初始的无序区 o 再将关键字最大的记录R1（即堆顶）和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key o 由于交换后新的根R1可能违反堆性质，故应

34、将当前无序区R1.n-1调整为堆。 o 重复2、3步骤，直到无序区只有一个元素为止。 · c+代码实现1. /* 2.  * 将数组arr构建大根堆 3.  * param arr 待调整的数组 4.  * param i   待调整的数组元素的下标 5.  * param len 数组的长度 6.  */ 7. void heap_adjust(

35、int arr, int i, int len) 8.  9.     int child; 10.     int temp; 11.  12.     for (; 2 * i + 1 < len; i = child) 13.

36、     14.         child = 2 * i + 1;  / 子结点的位置 = 2 * 父结点的位置 + 1 15.         / 得到子结点中键值较大的结点 16.  

37、0;      if (child < len - 1 && arrchild + 1 > arrchild) 17.             child +; 18.        

38、; / 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 19.         if (arri < arrchild) 20.          21.             temp = 

39、;arri; 22.             arri = arrchild; 23.             arrchild = temp; 24.          25.  

40、0;      else 26.             break; 27.      28.  29.  30. /* 31.  * 堆排序算法 32.  */ 33. void heap_sort(int arr, int 

41、len) 34.  35.     int i; 36.     / 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素 37.     for (int i = len / 2 - 1; i >= 0; i-) 38.     &

42、#160;39.         heap_adjust(arr, i, len); 40.      41.  42.     for (i = len - 1; i > 0; i-) 43.      44.  

43、0;      / 将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的 45.         int temp = arr0; 46.         arr0 = arri; 47.      &

44、#160;  arri = temp; 48.         / 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 49.         heap_adjust(arr, 0, i); 50.      51.  【编辑推荐】1. 2. 3. 4. 5.专心-专注-专业