#include<iostream>#include<cstdio>#define INF 999999#define MAXSIZE 20usingnamespacestd;//选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法//冒泡排序、插入排序、归并排序和基数排序都是稳定的排序算法。//直接插入排序，最好o(n),最差o(n^2)平均时间复杂度：o(n^2)，空间复杂度 o(1)void InserSort(int*a,int n){for (int i =1; i<n; i++){int j = i -1, temp = a[i];while (j >=0 && temp<a[j]){            a[j +1] = a[j];            j--;        }        a[j +1] = temp;    }}//获得排好的数组序void getOrder(int* a,int n){for (int i =0; i<n; i++){printf("%d ", a[i]);    }printf("\n");}//还原序列，方便下次测void backOrder(int* a,int n){for (int i =0; i<n; i++)a[i] = n - i;}//折半插入排序,最好情况o(nlogn) ,最差情况o(n^2),空间复杂度o(1)void binaySort(int* a,int n){for (int i =1; i<n; i++){int left =0, right = i -1;while (left<right){int mid = (left + right) /2;if (a[i] >= a[mid])left = mid +1;else right = mid -1;        }int limit = a[i] >= a[left] ? left +1 : left, temp = a[i];for (int k = i -1; k >=0; k--)a[k +1] = a[k];        a[limit] = temp;    }}//最坏时间复杂度 o(n^2), 最好时间复杂度o(n),平均时间复杂度o(n^2),空间复杂度o(1)void BubbleSort(int *a,int n){int i, j, flag;for (int i =0; i<n -1; i++){        flag =0;for (int k =0; k<n - i -1; k++){if (a[k]>a[k +1]){int t = a[k +1];                a[k +1] = a[k];                a[k] = t;                flag =1;            }        }if (!flag)break;    }}//时间复杂度nlog2^n ，越接近无序时间复杂度越低，反之越高，空间复杂度为log2^nvoid QuickSort(int* a,int left,int right){if (left<right){int x = left, y = right, temp = a[left];while (x<y){while (x<y&&a[y] >= temp)y--;            a[x] = a[y];while (x<y&&a[x] <= temp)x++;            a[y] = a[x];        }        a[x] = temp;        QuickSort(a, left, x -1);        QuickSort(a, x +1, right);    }}//时间复杂度o(n^2) ,空间复杂度o(1)void SelectSort(int* a,int n){for (int i =0; i<n -1; i++){int min = i, t;for (int k = i; k<n; k++){if (a[k]<a[min])min = k;        }        t = a[i];        a[i] = a[min];        a[min] = t;    }}//堆调整void heapAdjust(int*a,int s,int m){int temp = a[s];cout <<"a[s]==" << a[s] << endl;for (int j = s *2; j <= m; j *=2){if (j<m&&a[j +1]>a[j]){            j++;        }if (temp >= a[j]){break;//说明该节点本来就比左右子树大        }        a[s] = a[j];        s = j;//s指向交换后空的位置    }    a[s] = temp;}//堆排序, headAjust log2^n, 第一个循环(n/2)*log2^n, 第二个循环 n*log2^n 故该算法的时间复杂度为n*lpg2^nvoid HeapSort(int* a,int n){for (int i = n /2; i >=1; i--){        heapAdjust(a, i, n);    }for (int i = n; i >=1; i--){int temp = a[1];        a[1] = a[i];        a[i] = temp;        heapAdjust(a,1, i -1);    }}void merge(int* a,int* b,int* c ,int left,int middle,int right){int cnt = left,i=left,j=middle+1;while (i <=middle&&j <= right){if (a[i] < b[j]){            c[cnt] = a[i++];        }else{            c[cnt] = b[j++];        }        cnt++;    }if (i <= middle)while(i<=middle){        c[cnt] = a[i];        i++;        cnt++;    }if (j <= right)while(j<=right){        c[cnt] = b[j];        j++;        cnt++;    }}//对a,数组[left..right]合并排序到b ，时间复杂度o(nlogn^2),空间复杂度o(n)void mergeSort(int*a,int* b,int left,int right){if (left == right){        b[left] = a[right];    }else{int middle = (left + right) /2, temp1[MAXSIZE], temp2[MAXSIZE];        mergeSort(a, temp1, left, middle);        mergeSort(a, temp2, middle +1, right);        merge(temp1,temp2,b,left,middle,right);    }}int main(){int a[] = {0,10,9,8,7 };    mergeSort(a, a,1,4);for (int i =1; i <=4; i++)cout << a[i] <<" ";cout << endl;cout << endl;    system("pause");return0;}