C++/C实现各种排序算法（持续更新）--冒泡排序，选择排序，归并排序

2018 3 17

今日总结一下C++中的排序算法：

1冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。（来源百度百科）

C++实现：

 1 #include "stdafx.h"
 2 #include <iostream>
 3 using namespace std;
 4 int ha[] = {1,7,4,2,6,5,8,3};
 5 
 6 template <typename T>
 7 void Bubble_Sort(T *pDst,const int nLen)
 8 {
 9     int cycle;
10     //外层循环，控制遍历的次数（N-1(N为待排序的数组大小)）
11     for (cycle=0; cycle<(nLen-1) ; cycle++)
12     {
13         //内层循环，每次遍历到前一次最大值之前为止
14         for (int i=0; i < (nLen - 1-cycle); i++)
15         {
16             if (pDst[i] > pDst[i + 1])
17             {
18                 T tTemp = pDst[i];
19                 pDst[i] = pDst[i + 1];
20                 pDst[i + 1] = tTemp;
21             }
22         }
23     }
24 }
25 
26 int main()
27 {
28     //冒泡
29     
30     Bubble_Sort<int>(ha,8);
31     for (int i = 0; i < 8; i++)
32     {
33         printf("%d-",ha[i]);
34 　　　　 getchar();
35     }
36　　 return 0;
37 }

2 选择排序

　　工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

C++实现：

 1 //升序
 2 template <typename T>
 3 void Select_Sort(T *pDst, const int nLen)
 4 {
 5     T tTemp;
 6     
 7 //遍历nLen次，每次找到最小的值，交换
 8     for (int i = 0; i < nLen; i++)
 9     {
10         for (int j = i; j < nLen; j++)
11         {
12             if (pDst[j] <pDst[i])
13             {
14                  tTemp=pDst[i];
15                  pDst[i] = pDst[j];
16                  pDst[j] = tTemp;
17 
18             }
19             else
20                 continue;
21         }
22     }
23 
24 }
25 int main()
26 {
27     //冒泡
28     
29     //Bubble_Sort<int>(ha,8);
30     Select_Sort<int>(ha,8);
31     for (int i = 0; i < 8; i++)
32     {
33         printf("%d-",ha[i]);
34     }
35     return 0;
36 }

3 归并排序

将两个有序（同一种序）的数组合并为一个有序数组

（1）二路归并。二路归并的最好情况时间复杂度为：O(Min{sizof(a),sizeof(b)})

 1 // ConsoleApplication4.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include "atlstr.h"
 6 #include <iostream>
 7 #include <vector>
 8 using namespace std;
 9 //////
10 //二路归并排序。将两个表，合并成一个表的过程称为二路归并
11 //如：对两个y有序的数组 进行二路归并
12 const int a[] = {1,2,3};
13 const int b[] = {1,2,3,4,5,6,7};
14 
15 int* Merger_Sort(const int *a,const int *b,int nLen1,int nLen2)
16 {
17     int *pDst = new int[nLen1+nLen2];
18     int k = 0;
19     int i = 0;
20     int j = 0;
21     while (i < nLen1&&j < nLen2)
22     {
23         if (a[i] <= b[j])
24         {
25             pDst[k] = a[i];
26             i++;
27         }
28         else
29         {
30             pDst[k] = b[j];
31             j++;
32         }
33         k++;
34     }
35     while (i < nLen1)
36     {
37         pDst[k] = a[i];
38         i++;
39         k++;
40     }
41     while (j < nLen2)
42     {
43         pDst[k] = b[j];
44         j++;
45         k++;
46     }
47     return pDst;
48 }
49 
50 int main()
51 {
52     int *p = NULL;
53     p = Merger_Sort(a,b,3,7);
54     for (int i = 0; i <10; i++)
55     {
56         cout << p[i];
57     }
58     delete[] p;
59 
60     getchar();
61     return 0;
62 }

View Code

(2) 普通归并排序；将二路归并扩展到一般情况，将一个序列分为N组，每组都是一个有序的数组，对两两之间进行归并

  1 // ConsoleApplication7.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 //二路归并的前提是两个结构的元素已经是有序的（同样的顺序）
  6 int a[] = { 1,3,4,5,6 };
  7 int b[] = { 2,3,8,9,10,18 };
  8 void Two_MergeSort(int *pA1, int *pA2, int nA1Len, int nA2Len, int *pOut)
  9 {
 10     int i = 0; int j = 0;
 11     int nDstPos = 0;
 12     while (i < nA1Len&&j < nA2Len)
 13     {
 14         if (pA1[i] > pA2[j])
 15         {
 16             //找到同一顺序的元素中较小的放入pOut中
 17             pOut[nDstPos++] = pA2[j++];
 18         }
 19         else
 20             pOut[nDstPos++] = pA1[i++];
 21     }
 22     while (i < nA1Len)
 23     {
 24         pOut[nDstPos++] = pA1[i++];
 25     }
 26     while (j<nA2Len)
 27     {
 28         pOut[nDstPos++] = pA2[j++];
 29     }
 30 }
 31 
 32 //输入的Pos指的是坐标,可以比较一下与二路归并的区别
 33 void General_Two_MergeSort(int *pA, int nStartPos, int nMidPos, int nEndPos, int *pOut)
 34 {
 35     int i = nStartPos;
 36     int j = nMidPos + 1;
 37     int k = nEndPos;
 38     int nDstPos = nStartPos;
 39     printf("对区间[%d,%d]和区间[%d,%d]进行排序
", nStartPos, nMidPos, nMidPos + 1, nEndPos);
 40     while (i <= nMidPos&&j <= nEndPos)
 41     {
 42         if (pA[i] > pA[j])
 43         {
 44             pOut[nDstPos++] = pA[j++];
 45         }
 46         else
 47         {
 48             pOut[nDstPos++] = pA[i++];
 49         }
 50     }
 51     while (i <= nMidPos)
 52     {
 53         pOut[nDstPos++] = pA[i++];
 54     }
 55     while (j <= nEndPos)
 56     {
 57         pOut[nDstPos++] = pA[j++];
 58     }
 59     for (int n = nStartPos; n <= nEndPos; n++)
 60     {
 61         pA[n] = pOut[n];
 62     }
 63     static int nCount = 0;
 64     printf("第%d次调用
",++nCount);
 65     //printf("参数分别是：StartPos:%d,MidPos:%d,EndPos:%d
", nStartPos,nMidPos,nEndPos);
 66     //printf("当前排序的成员有%d个，分别是：
",nEndPos-nStartPos+1);
 67     for (int n = nStartPos; n <= nEndPos; n++)
 68     {
 69         printf("%d ",pOut[n]);
 70     }
 71     printf("
");
 72     printf("
");
 73     printf("
");
 74 }
 75 
 76 
 77 //推广到更普通的归并排序
 78 //归并排序的核心是将一串数字中的数字分成两组，先对分成的每一组进行深度归并，最后再对初始的两组进行归并
 79 void Merge_Sort(int *pA, int nLow, int nHigh, int *pOut)
 80 {
 81     if (nLow < nHigh)
 82     {
 83         int nMid = (nLow + nHigh) / 2;
 84         //左边递归，直到只含有一个元素
 85         Merge_Sort(pA, nLow, nMid, pOut);
 86         //右边递归，直到只含有一个元素
 87         Merge_Sort(pA, nMid + 1, nHigh, pOut);
 88         //对两个元素进行递归排序
 89         General_Two_MergeSort(pA, nLow, nMid, nHigh, pOut);
 90     }
 91 
 92 
 93 }
 94 
 95 
 96 int main()
 97 {
 98     int c[7] = { 0 };
 99     int Dst[] = { 1,3,5,7,9,11,13 };
100     //Two_MergeSort(a,b,5,6,c);
101     Merge_Sort(Dst, 0, 6, c);
102     int i = 0;
103     while (i < 7)
104     {
105         printf("%d ", c[i++]);
106     }
107 
108 
109     getchar();
110     return 0;
111 }

View Code

C++/C实现各种排序算法（持续更新）--冒泡排序，选择排序，归并排序

相关推荐