归并排序的非递归算法

  1 //编译运行环境：VS2012
  2 #include<iostream>
  3 #include<stdlib.h>
  4 using namespace std;
  5 int countbody = 0;
  6 //交换数组中两个元素的位置
  7 void swap(int left, int right, int sort[]){
  8 
  9     int temp;
 10     temp = sort[left];
 11     sort[left] = sort[right];
 12     sort[right] = temp;
 13 
 14 }
 15 
 16 //两个已经排好序的小数组整合成较大的数组
 17 void bodySort(int midnum, int leftstart, int rightEnd, int sort[]){
 18 
 19     
 20     for (int i = midnum; i >= leftstart; i--,midnum--)
 21     {
 22         for (int j = midnum; j < rightEnd; j++)
 23         {
 24             countbody ++;
 25             if(sort[j] > sort[j+1]) swap(j,j+1,sort);
 26             else break;
 27         }
 28 
 29     }
 30     
 31 }
 32 
 33 //归并排序进行的拆分工作
 34 void marginSort(int sortnum, int sortArray[]){
 35 
 36     int* tempSort = (int*)malloc(sortnum*sizeof(int));
 37     int tm = 0;
 38     for (int i = 0; i < sortnum-1; i++)
 39     {
 40         if(sortArray[i+1] < sortArray[i]){
 41             tempSort[tm++] = i;
 42         }
 43     }
 44     tempSort[tm++] = sortnum-1;
 45     int count = 1;
 46     /***************************************************************/
 47     cout << "第"<< count++ <<"次归并：" << endl;
 48     cout << "tempSort的初始情况：" << endl;
 49     cout << "tempSort.size == " << tm << endl;
 50     for (int i = 0; i < tm; i++)
 51     {
 52         cout << "tempSort["<<i<<"]==" << tempSort[i] << " ";
 53     }
 54     cout << endl;
 55     cout << endl;
 56     /***************************************************************/
 57     
 58     while (tm != 1)
 59     {
 60         countbody = 0;
 61 
 62         cout << "第"<< count++ <<"次归并：" << endl;
 63 
 64         int tmfl = tm % 2 == 0 ? tm : tm - 1;
 65         for (int i = 0; i < tmfl; i += 2)
 66         {
 67             int startNum = 0;
 68             if(i != 0)
 69                 startNum = tempSort[i-1]+1;
 70              bodySort(tempSort[i],startNum,tempSort[i+1],sortArray);
 71         }
 72         int ff = 0;
 73         
 74         for (int i = 1; i < tmfl; i += 2)
 75         {
 76             tempSort[ff++] = tempSort[i];
 77         }
 78         if((tm) % 2 != 0){
 79             
 80             tempSort[ff++] = tempSort[tm-1];
 81             
 82         }    
 83         tm = ff;
 84         /***************************************************************/
 85         cout << "比较次数：" << countbody << endl;
 86         cout << "tempSort的情况：" << endl;
 87         cout << "tempSort.size == " << tm << endl;
 88         for (int i = 0; i < tm; i++)
 89         {
 90             cout << "tempSort["<<i<<"]==" << tempSort[i] << " ";
 91         }
 92         cout << endl;
 93         cout << endl;
 94         /***************************************************************/
 95     }
 96 
 97     free(tempSort);
 98 }
 99 
100 
101 int main ()//函数的功能:归并排序的非递归算法
102 {
103 
104     int* sortArray;
105     int sortnum = 0;
106     
107     cout << "请输入要排序的元素的长度:" << endl;
108     cin >> sortnum;
109     sortArray = (int*)malloc(sortnum*sizeof(int));
110     if(sortArray == NULL){
111         cout << "不能成功分配存储空间！";
112         exit(1);
113     }
114     cout << "请输入元素:" << endl;
115     for (int i = 0; i < sortnum; i++)
116     {
117         cin >> sortArray[i];
118     }
119 
120     marginSort(sortnum,sortArray);
121     
122     cout << "排序后的数组元素为：" << endl;
123     for (int i = 0; i < sortnum; i++)
124     {
125         cout << sortArray[i] << " ";
126     }
127     free(sortArray);
128     
129 }