常用排序算法总结——数据结构.ppt

排序的时间复杂性 折半插入效率分析 希尔排序效率分析 快排序（Quick Sort) 快排序（Quick Sort) 快排序---分割过程 快排序是一个分治算法（也是第一个） 快排序的关键过程是每次递归的分割过程 分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边 分割算法： 用临时变量对轴备份 取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high 移动两个指针 首先从high所指的位置向左搜索，找到第一个小于轴的元素, 把这个元素放在low的位置 再从low开始向右，找到第一个大于轴的元素，把它放在high的位置 快排序（Quick Sort) 快排序---分割过程 分割算法： 重复上述过程，直到low=high， 把轴放在low所指的位置 这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边 快排序（Quick Sort) 快排序---分割过程 快排序（Quick Sort) 快排序---分割过程 int Partition(T Array[], int low, int high){ T pivot = Array[low]; // while(low high){ //在作为快排序的子程序时不用 while(low high Array[high] = pivot) high --; Array[low] = Array[high]; while(low high Array[low] = pivot) low++; Array[high] = Array[low]; //} //在作为快排序的子程序时不用 Array[low] = pivot; return low; } 快排序（Quick Sort) 快排序---算法 快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1 快排序（Quick Sort) 快排序---算法 void QuickSort(T Array[], int low, int high){ int PivotLocation; if(low high){ PivotLocation = Partition(Array, low, high); QuickSort(Array, low, PivotLocation-1); QuickSort(Array, PivotLocation+1, high); } } 归并排序（Merge Sort) 归并---合并两个有序的序列 假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2) 方法很简单：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并， 其复杂度为O(n) 归并排序（Merge Sort) 归并---合并两个有序的序列 归并排序（Merge Sort) 归并---合并两个有序的序列 void merge(T A[], int Alen, T B[], int Blen, T C[]){ int i=0,j=0,k=0; while(i Alen j Blen){ if(A[i] B[j]) C[k++] = A[i++]; else C[k++] = B[j++]; } while(i Alen) C[k++] = A[i++]; while(j Blen) C[k++] = B[j++]; } 归并排序（Merge Sort) 归并---合并一个序列中的两个有序的数据段 void merge(T A[], int l, int m, int h){ int i=l,j=m+1,k=0; T *C = new T[h-l+1]; while(i = m j = h){ if(A[i] A[j]) C[k++] = A[i++]; else C[k++] = A[j++]; } while(i