#include
using namespace std; //归并排序非递归版。 void Sort(int a[], int n,int high) { int k; for (int i = 0; i < high; i += 2 * n) { int x = i;//001 int y = i + n;//2 2 3 int z = i + 2 * n;// 4 if (z>high) { z = high; } for (int j = y; j <= z; j++) { int temp = a[j]; for (k = j; k > 0; k--) { if (a[k - 1]>temp) { a[k] = a[k - 1]; } else { break; } } a[k] = temp; //在需要合并的时候，我选择使用插入排序，不开辟新的空间。 } } } void Grial(int a[],int high) { int n = high / 2+1;//终止位置。 //1 2 3 for (int i = 1; i <= n; i *= 2) { Sort(a,i,high); } } int main() { int a[] = { 5,4,3,7,1,3,2,0,5,6,7,9,654,5,423,3,4, 5,6,8,523,423,4,5,6,7,8,45,6,53,423,4,100 }; Grial(a,sizeof(a) / sizeof(int)-1); for (int i = 0; i < sizeof(a) / sizeof(int);i++) { cout << a[i] << ; } cout << endl; return 0; }
#include
using namespace std; //递归版本的归并排序。 void Sort(int a[], int low, int mid, int high) { int i; int j; int temp; for (i = mid+1; i <= high; i++) { temp = a[i]; for (j = i; j > low;j--) { if (temp < a[j - 1]) { a[j] = a[j-1]; } else { break; } } //既然已经接近排序好的，那么我们可以选择使用插入排序或者冒泡排序来提高效率 //并且不开辟额外的空间。 a[j] = temp; } } void Sert(int a[],int low,int high) { if (low >= high)return; int mid = (low + high) / 2; Sert(a,low, mid); Sert(a, mid + 1, high); Sort(a,low,mid,high); } int main() { int a[] = {6,2,1,3,4,-1,2-3,4,5,6,7,532,4,432,-23, -32,1,-3,21,-321,-3,5,6,8,432,5,66,991}; Sert(a, 0,sizeof(a) / sizeof(int)-1); for (int i = 0; i < sizeof(a) / sizeof(int); i++) { cout << a[i] << ; } cout << endl; return 0; }
?