希尔排序 希尔(shell)排序是插入排序的一种。也称缩小增量排序 ,是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序。希尔排序是按照记录下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量减少,每组包含的关键词增多,当增量减少至1时,所有元素被分为1组,算法结束。 我们分割待排序记录的目的是减少待排序记录的个数,并使整个序列向基本有序发展。而如上面这样分完组后,就各自排序的方法达不到我们的要求。因此,我们需要采取跳跃分割 的策略:将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 template <typename E>void inssort (E A[],int n,int incr) { for (int i = incr;i < n;i += incr){ for (int j = i;(j > incr) && (A[j] < A[j-incr]);j -= incr) swap (A,j,j - incr); } } template <typename E>void shellsort (E A[],int n) { for (int i = n/2 ;i > 2 ;i /= 2 ) for (int j = 0 ;j < i;j ++) inssort <E>(A[j],n-j,j); inssort <E,Comp>(A,n,1 ); }
快速排序 一趟快速排序思想 1、目标:找一个记录,以它的关键字作为枢轴 ,凡其关键字小于枢轴的记录均移动至该记录之前,反之,凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后,记录的无序序列A[s..t]将分割成两部分: A[s..i-1]和A[i+1..t],且A[j].key(左边)≤ A[i].key(枢轴) ≤ A[k].key(右边) 2、首先对无序的记录序列进行“一次划分”,之后分别对分割所得的两个子序列“递归”进行快速排序。 3、一趟快速排序的过程 a. 首先选定轴,交换轴与最后一个元素;(最后要交换回来) b. 设定l指针指向第一个元素前的位置,r指向最后元素; c. 先移动l,遇到比轴大则停止;再移动r,遇到比轴小停止,交换l和r所指元素。 d. 持续执行上一步,直到l和r相遇; e. 将最后一个元素和停止时l(r)位置的元素交换。 4、代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 template <typename E>inline int findpivot (E A[],int i,int j) { return (i+j)/2 ; }template <typename E>int partition (E A[],int l,int r,E& pivot) { do { while (A[++l] < pivot); while ((l < r) && A[--r] > pivot); swap (A,l,r); }while (l < r) return l; } template <typename E>void qsort (E A[],int i,int j) { if (j <= i)return ; int pivotindex = findpivot (A,i,j); swap (A,pivotindex,j); int k = partition <E>(A,i-1 ,j,A[j]); swap (A,k,j); qsort <E>(A,i,k-1 ); qsort <E>(A,k+1 ,j); }
5、时间复杂度 假设一次划分所得枢轴位置 i=k,则对n个记录进行快排所需时间: T(n) = Tpass(n) + T(k-I) + T(n-k), 其中 Tpass(n)为对 n 个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的,则 k 取 1 至 n 中任意一值的可能性相同。 由此可得快速排序所需时间的平均值为:结论 : 快速排序的时间复杂度为O(nlogn)。 若待排记录的初始状态为按关键字有序时,快速排序将蜕化为起泡排序,其时间复杂度为O(n^2)。
合并(归并)排序 算法思想: 例如: 伪代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 template <tyepname E>void merge (E A[],E temp[],int left,int right) { if (left == right) return ; int mid = (left+right)/2 ; mergesort <E>(A,temp,left,mid); mergesort <E>(A,temp,mid+1 ,right); for (int i = left;i <= right;i ++) temp[i] = A[i]; int i1 = left,i2 = mid + 1 ; for (int curr = left; curr <= right;curr ++){ if (i1 == mid + 1 ) A[curr] = temp[i2++]; else if (i2 > right) A[curr] = temp[i1++]; else if (temp[i1] < temp[i2]) A[curr] = temp[i1++]; else A[curr] = temp[i2++]; } }
时间复杂度:O(nlogn) 时间复杂度:O(n)