本文共 4409 字,大约阅读时间需要 14 分钟。
排序是一种操作,一种对原本无序的序列通过按关键字进行元素值交换达到增序排列或降序排列的操作
。元素是否完全在内存中
分为:内部排序和外部排序。内部排序又可细分为:插入排序(直接插入排序、折半插入排序和希尔排序)、交换排序(冒泡排序、快速排序)、选择排序(简单选择排序和堆排序)、归并排序和基数排序。
外部排序只有多路归并排序
。待排序表中关键字相等的元素的前后关系在经过排序操作后依旧能够保持,如 ab 经过排序后还是 ab
。不具有这种性质的算法则称不具有稳定性。值得注意的时,算法稳定性作为衡量标准时,待排序的表一定是允许关键字重复的;否则,算法稳定性便没有任何意义。每次将一个待排序的记录按期关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成
。符合这种算法思想的排序算法都称为插入排序,主要有直接插入排序、折半插入排序和希尔排序
。// 直接插入排序// 数组的 0 下标不存放实际元素void InsertSortDirectly(int a[], int len){ int i, j; for (i = 2; i <= len; i++) { if (a[i] < a[i - 1]) { // 复制为哨兵 a[0] = a[i]; for (j = i - 1; a[0] < a[j]; --j) a[j + 1] = a[j]; a[j + 1] = a[0]; } }}
直接插入排序适用于顺序存储和链式存储的线性表
。// 折半插入排序void InsertSortUndirectly(int a[], int len){ int i, j, low, high, mid; for (i = 2; i <= len; i++) { a[0] = a[i]; low = 1; high = i - 1; while (low <= high) { mid = (low + high) / 2; if (a[mid] > a[0]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= high + 1; --j) a[j + 1] = a[j]; a[high + 1] = a[0]; }}
缩小增量排序
。将待排序的表分割成若干形如L[i, i+d, i+2d, ... ,i+kd] 的 “特殊” 子表,即将相隔某个增量的记录组成子表,对各个子表进行直接插入排序,然后再对整个表进行一次直接插入排序
。 // 希尔排序void ShellSort(int a[], int len){ int dk, i, j; for (dk = len / 2; dk >= 1; dk = dk / 2) // dk 表示步长 { for (i = dk + 1; i <= len; ++i) { if (a[i] < a[i - dk]) // 将 a[i] 插入有序增量子表 { a[0] = a[i]; for (j = i - dk; j > 0 && a[0] < a[j]; j -= dk) a[j + dk] = a[j]; //记录后移,查找插入位置 a[j + dk] = a[0]; } } }}
// 冒泡排序void BubbleSort(int a[], int len){ // 标志是否发生交换 bool flag = false; for (int i = 0; i < len - 1; i++) { flag = false; for (int j = len - 1; j > i; j--) { if (a[j - 1] > a[j]) { int t = a[j - 1]; a[j - 1] = a[j]; a[j] = t; } flag = true; } if (flag == false) return; }}
在待排序表工[1.n]中任取一个元素pivot作为枢轴,通过一趙排序将待排序表划分为独立的两部分エ[1.k-1]和エ[k+1.n],使得[1…k-1]中的所有元素小于 pivot,L[k+1...n]中的所有元素大于等于 pivot,则 pivot放在了其最终位置L(k)上,这个过程称为一趟快速排序。然后分别递归地对两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。
一趟快速排序的过程就是一个交替搜索和交换的过程。// 快速排序int Partition(int a[], int low, int high){ int pivot = a[low]; while (low < high) { while (low < high && a[high] >= pivot) --high; a[low] = a[high]; while (low < high && a[low] <= pivot) ++low; a[high] = a[low]; } a[low] = pivot; return low;}void QuickSort(int a[], int low, int high){ if (low < high) { // 划分 int pivotpos = Partition(a, low, high); QuickSort(a, low, pivotpos - 1); QuickSort(a, pivotpos + 1, high); }}int main(){ int a3[] = { 49,38,65,97,76,13,27,49 }; cout << endl << "快速排序:"; QuickSort(a3, 0, 7); for (int i = 0; i < 8; i++) cout << a3[i] << " "; return 0;}
选取头尾和中间元素三者的中间值作为最终的轴枢元素
,还有就是从待排序表中随机选取一个;理想情况下,轴枢元素前后的元素个数都不大于n/2,此时时间复杂度为O(nlog2n)。快速排序是所有内部排序算法中平均性能最优的排序算法
,因为快速排序的平均情况下的运行时间与最佳情况下的运行时间很接近。转载地址:http://fhqgn.baihongyu.com/