数据排序

明确：实际应用中，直接用sort()函数就好了，但是学习过程还是多了解点东西比较好，而且排序过程中运用的思想也很重要

例1.直接插入排序

        从左往右处理数据，每处理一个数据，就将这个数据从当前位置的前一个位置开始往前比较，直到找到小于它的数据，然后插在它的前面（以从小到大排序为例）。稳定。

void InsertionSort(int R[],int n){ //对R[1]...R[n]排序for(int i=2; i<=n; i++){ int K=R[i], j=i-1;while(j>=1 && R[j]>K){R[j+1]=R[j];j--;}R[j+1]=K;}
}

例2.冒泡排序

        每次循环找到当前最大的，并把它放到队尾相应的位置。然后进行多次循环。稳定。

void SimpleBubbleSort(int R[], int n){for(int bound=n; bound>=2; bound--)for(int i=1; i<bound; i++)if(R[i] > R[i+1]) swap(R[i],R[i+1]);
}

例3.直接选择排序

        每次选出除了已经排好序外的最大的数值，最后进行一次交换。进行n-1次该操作。不稳定。

例4.希尔排序

        将元素分为d组，对每组使用直接插入排序，将直接插入排序的步调定为d，然后d值逐渐减小，直至为1。在逻辑上感觉复杂度没有很大变化，但是在执行过程中会变快。

void ShellSort(int R[], int n){ //对R[1]…R[n]递增排序for(int d=n/2; d>0; d/=2) //d为增量值for(int i=d+1; i<=n; i++){ //.....R[i-3d], R[i-2d], R[i-d] <-R[i]//把直接插入排序的步调换成了dint K=R[i],j=i-d; //指针j从右往左扫描本组元素while(j>0 && R[j]>K){//在本组从右往左找第1个<=K的元素R[j+d]=R[j];j-=d;}R[j+d]=K;}
}

例5.堆排序

        按照二叉树的结构，每次选出最大的，只要logn的时间，这样时间复杂度就会降到nlogn

        选出最大的就是在二叉树中从叶结点的父节点开始将该结点与它左右孩子结点的值进行比较，将最大值与父结点进行交换。这样一层一层往上，就可以保证根结点是最大的。同时完全二叉树的结点编号与数组有着对应关系。比如，结点i的左孩子是2i，右孩子是2i+1。这样就可以确定最大的不是叶结点的编号是n/2。

void ShiftDown(int R[], int n, int i) { 
//堆元素R[i]下沉, 数组R[ ]存储堆, n为堆包含的元素个数while(i <= n/2){ //i最多下行至最后一个非叶结点int maxchd = 2*i; // 假定最大孩子为左孩子if(maxchd+1<=n && R[maxchd]<R[maxchd+1]) maxchd++; //i的右孩子是最大孩子if(R[i] >= R[maxchd]) return;swap(R[maxchd],R[i]); // R[i]的最大孩子比R[i]大i = maxchd; // 结点i继续下沉}
}void BuildHeap(int R[],int n){for(int i=n/2; i>=1; i--)ShiftDown(R,n,i); //建立以i为根的堆，即下沉i
}void HeapSort(int R[],int n){ //堆排序R[1]…R[n]BuildHeap(R, n); //将R建为堆for(int i=n; i>1; i--){ //i为当前堆的堆尾swap(R[1], R[i]); //前i个元素的最大者R[1]与R[i]交换ShiftDown(R,i-1,1); //下沉R[1]使R[1]...R[i-1]重建为堆}
}

例6.快速排序

        快速排序就是选取基准元素，然后将数组的元素分割成，小于等于该元素的，和大于该元素的。每次循环，将小于等于该元素的往左放，大于该元素的往右放，这样每次循环就可以确认出该元素的位置，同时将数组分成两个小数组再次处理。

        这种处理数据的方式还可以转化到多个方面方面，比如三路分划。

int Partition(int R[], int m, int n){ //对子数组Rm…Rn分划int K=R[m], L=m+1, G=n; //Rm为基准元素while(L<=G) {while(L<=n && R[L]<=K) L++; //从左向右找第一个>K的元素while(R[G]>K) G--; //从右向左找第一个K的元素if(L<G) {swap(R[L],R[G]); L++; G--;}} swap(R[m],R[G]); return G; 
}void QuickSort(int R[], int m, int n){ //对Rm…Rn递增排序if(m < n){int k=Partition(R, m, n);QuickSort(R, m, k-1);QuickSort(R, k+1, n);}
}

例7.归并排序

        归并排序就是把数组分成两部分，递归调用，然后对这两部分进行归并。就是再开一个数组，然后从小到大对该数组进行合并。像单链表的排序就非常适合归并排序。

void Merge(int R[],int low, int mid, int high){
//将两个相邻的有序数组(Rlow,…,Rmid)和(Rmid+1,…,Rhigh)合并成一个有序数组int i=low, j=mid+1, k=0;int *X=new int[high-low+1];while(i<=mid && j<=high)if(R[i]<=R[j]) X[k++]=R[i++];else X[k++]=R[j++];while(i<=mid) X[k++]=R[i++]; //复制余留记录while(j<=high) X[k++]=R[j++];for(i=0; i<=high-low; i++) //将X拷贝回RR[low+i]=X[i];delete []X;
}void MergeSort(int R[], int m, int n){if(m < n){int k = (m+n)/2; //将待排序序列等分为两部分MergeSort(R, m, k);MergeSort(R, k+1, n);Merge(R, m, k, n);}
}

        还可以变形，进行非递归调用。两种方法考题经常会问非递归调用的方法。

void Merge(int R[],int low, int mid, int high){
//将两个相邻的有序数组(Rlow,…,Rmid)和(Rmid+1,…,Rhigh)合并成一个有序数组int i=low, j=mid+1, k=0;int *X=new int[high-low+1];while(i<=mid && j<=high)if(R[i]<=R[j]) X[k++]=R[i++];else X[k++]=R[j++];while(i<=mid) X[k++]=R[i++]; //复制余留记录while(j<=high) X[k++]=R[j++];for(i=0; i<=high-low; i++) //将X拷贝回RR[low+i]=X[i];delete []X;
}void MergePass(int R[], int n, int L){int i;for(i=1; i+2*L-1<=n; i+=2*L)Merge(R, i, i+L-1, i+2*L-1);
//处理余留的长度小于2*L的子数组if(i+L-1<n)Merge(R, i, i+L-1, n); //L<剩余部分长度<2L
}

        用这种方法还可以求逆序对的个数，就是在不满足前一个数组小于后一个数组时，用全局变量cnt+=mid-i+1这样就可以求解了。不过这种方法就是，在求逆序对的时候很好用，但是平时我也想不出来它还能有什么应用。