常见基本排序算法 不念不忘少年蓝@ 2022-10-08 14:21 117阅读 0赞 ### 文章目录 ### * 直接插入排序 * 希尔排序 * 归并排序 * 快速排序 * 应用 # 直接插入排序 # 一个一个逐步插入 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70] //直接插入排序 void InsertSort(SqList& L) { int i, j; for (i = 2; i <= L.length; i++) { InsertSortCount++; if (L.r[i].key < L.r[i - 1].key) //小于时,将R[i]插入有序表 { L.r[0] = L.r[i]; // R[0]作监测哨兵 L.r[i] = L.r[i - 1]; for (j = i - 2; L.r[0].key < L.r[j].key; j--) { InsertSortCount++; L.r[j + 1] = L.r[j]; //记录后移 } L.r[j + 1] = L.r[0]; //插入到正确位置 } } } # 希尔排序 # ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1] //希尔排序 void ShellInsert(SqList& L,int dk) //步长为dk的插入排序 { int i, j; for (i = dk + 1; i <= L.length; i++) { ShellSortCount++; if (L.r[i].key < L.r[i - dk].key) //小于时,需将r[i]插入有序表 { L.r[0] = L.r[i]; //为统一算法设置监视哨 for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk) { L.r[j + dk] = L.r[j]; //记录后移 } L.r[j + dk] = L.r[0]; //插入到正确位置 } } } void ShellSort(SqList& L,int dita[],int t) { //按增量序列dlta[0,1…,t-1]对顺序表S作希尔排序 for (int k = 0;k < t;k++) ShellInsert(L,dita[k]); } # 归并排序 # ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2] //归并排序算法 void Merge(RedType SR[], RedType TR[], int i, int m, int n) { int j, k; for (j = m + 1, k = i; i <= m && j <= n; k++) { MergeSortCount++; if (SR[i].key <= SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } while (i <= m) TR[k++] = SR[i++]; while (j <= n) TR[k++] = SR[j++]; } void Msort(RedType p1[], RedType p2[], int n, int l) { int i = 1, j; while (i + 2 * l - 1 <= n) { Merge(p1, p2, i, i + l - 1, i + 2 * l - 1); i = i + 2 * l; } if (i + l <= n) Merge(p1, p2, i, i + l - 1, n); else for (j = i; j <= n; j++) p2[j] = p1[j]; } void MergeSort(SqList& L) { int l = 1; RedType s[101]; while (l < 100) { Msort(L.r, s, L.length, l); l = l * 2; Msort(s, L.r, L.length, l); l = l * 2; } } # 快速排序 # ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3] //快速排序 int Partition(SqList& L, int low, int high) { L.r[0] = L.r[low]; //以子表的第一个记录作为轴值记录 int pivotkey = L.r[low].key; //取轴值记录关键字 while (low < high) //从表的两端交替地向中间扫描 { QSortCount++; while (low < high && L.r[high].key >= pivotkey) high--; if (low < high) L.r[low++] = L.r[high]; //将比轴值记录小的交换到低端 while (low < high && L.r[low].key <= pivotkey) low++; if (low < high) L.r[high--] = L.r[low]; } //将比轴值记录大的交换到高端 L.r[low] = L.r[0]; //轴值（支点）记录到位 return low; //返回轴值（支点）记录所在位置 } void QSort(SqList& L, int low, int high) { //对顺序表L中的子序列L.r[low…high]作快速排序 if (low < high) { int pivotloc = Partition(L, low, high); QSort(L, low, pivotloc - 1); //对小于轴值序列实现递归排序 QSort(L, pivotloc + 1, high); } //对大于轴值序列实现递归排序 } # 应用 # 例题： 随机产生100 个整数构成的序列, 分别以直接插入、希尔、快速、归并等排序算法排序, 并统计各自的比较次数 /* 3、随机产生100 个整数构成的序列, 分别以直接插入、希尔、快速、归并等排序算法排序, 并统计各自的比较次数 */ #include <iostream> using namespace std; typedef int KeyType; typedef int InfoType; # define Maxsize 200 //待排序序列中记录的最大个数 # define T 7 int InsertSortCount = 0, ShellSortCount = 0, QSortCount = 0, MergeSortCount = 0; // 待排序表中每个数据元素的数据类型定义 typedef struct { KeyType key; //表示排序关键字 //InfoType otherinfo; //排序记录中的其他所有数据项 } RedType; // 待排序数据表的数据类型定义 typedef struct { RedType r[Maxsize + 1]; //存放待排序全体记录 int length; //排序记录个数 } SqList; //直接插入排序 void InsertSort(SqList& L) { int i, j; for (i = 2; i <= L.length; i++) { InsertSortCount++; if (L.r[i].key < L.r[i - 1].key) //小于时,将R[i]插入有序表 { L.r[0] = L.r[i]; // R[0]作监测哨兵 L.r[i] = L.r[i - 1]; for (j = i - 2; L.r[0].key < L.r[j].key; j--) { InsertSortCount++; L.r[j + 1] = L.r[j]; //记录后移 } L.r[j + 1] = L.r[0]; //插入到正确位置 } } } //希尔排序 void ShellInsert(SqList& L,int dk) //步长为dk的插入排序 { int i, j; for (i = dk + 1; i <= L.length; i++) { ShellSortCount++; if (L.r[i].key < L.r[i - dk].key) //小于时,需将r[i]插入有序表 { L.r[0] = L.r[i]; //为统一算法设置监视哨 for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk) { L.r[j + dk] = L.r[j]; //记录后移 } L.r[j + dk] = L.r[0]; //插入到正确位置 } } } void ShellSort(SqList& L,int dita[],int t) { //按增量序列dlta[0,1…,t-1]对顺序表S作希尔排序 for (int k = 0;k < t;k++) ShellInsert(L,dita[k]); } //快速排序 int Partition(SqList& L, int low, int high) { L.r[0] = L.r[low]; //以子表的第一个记录作为轴值记录 int pivotkey = L.r[low].key; //取轴值记录关键字 while (low < high) //从表的两端交替地向中间扫描 { QSortCount++; while (low < high && L.r[high].key >= pivotkey) high--; if (low < high) L.r[low++] = L.r[high]; //将比轴值记录小的交换到低端 while (low < high && L.r[low].key <= pivotkey) low++; if (low < high) L.r[high--] = L.r[low]; } //将比轴值记录大的交换到高端 L.r[low] = L.r[0]; //轴值（支点）记录到位 return low; //返回轴值（支点）记录所在位置 } void QSort(SqList& L, int low, int high) { //对顺序表L中的子序列L.r[low…high]作快速排序 if (low < high) { int pivotloc = Partition(L, low, high); QSort(L, low, pivotloc - 1); //对小于轴值序列实现递归排序 QSort(L, pivotloc + 1, high); } //对大于轴值序列实现递归排序 } //归并排序算法 void Merge(RedType SR[], RedType TR[], int i, int m, int n) { int j, k; for (j = m + 1, k = i; i <= m && j <= n; k++) { MergeSortCount++; if (SR[i].key <= SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } while (i <= m) TR[k++] = SR[i++]; while (j <= n) TR[k++] = SR[j++]; } void Msort(RedType p1[], RedType p2[], int n, int l) { int i = 1, j; while (i + 2 * l - 1 <= n) { Merge(p1, p2, i, i + l - 1, i + 2 * l - 1); i = i + 2 * l; } if (i + l <= n) Merge(p1, p2, i, i + l - 1, n); else for (j = i; j <= n; j++) p2[j] = p1[j]; } void MergeSort(SqList& L) { int l = 1; RedType s[101]; while (l < 100) { Msort(L.r, s, L.length, l); l = l * 2; Msort(s, L.r, L.length, l); l = l * 2; } } void display(SqList L) { for (int i = 1; i <= 100; i++) { cout << L.r[i].key << "\t"; if (i % 10 == 0) { cout << endl; } } } int main() { //int a[800]; ///* //rand() % n +a; //其中的a是起始值，n-1+a是终止值，n是整数的范围 //*/ //for (int i = 0; i < 100; i++) { // a[i] = rand() % 200 + 1; //} SqList L; L.length = 100; for (int i = 1; i <= 100; i++) { L.r[i].key = rand() % 200 + 1; } cout << "随机生成的100个数：" << endl; display(L); int dita[T] = { 49,37,29,23,19,11,1 }; int c = 1; while (c) { cout << "+=====================================+" << endl; cout << "| 1.直接插入排序 |" << endl; cout << "| 2.希尔 |"<< endl; cout << "| 3.快速 |"<< endl; cout << "| 4.归并 |" << endl; cout << "| 0.退出 |" << endl; cout << "+=====================================+" << endl; cout << "请选择："; cin >> c; switch (c) { case 1: cout << endl << "直接插入排序：" << endl; InsertSort(L); display(L); cout << "比较次数：" << InsertSortCount << endl; cout << endl; break; case 2: cout << endl << "希尔:" << endl; ShellSort(L, dita, T); display(L); cout << "比较次数：" << ShellSortCount << endl; cout << endl; break; case 3: cout << endl << "快速:" << endl; QSort(L, 0, 100); display(L); cout << "比较次数：" << QSortCount << endl; cout << endl; break; case 4: cout << endl << "归并:" << endl; MergeSort(L); display(L); cout << "比较次数：" << MergeSortCount << endl; cout << endl; break; default: break; } } //int dita[10]; //int t = 10; //for (int i = 0; i < t; i++) { // if (i == 0) { // dita[0] = 49; // } // else { // dita[i] = dita[i - 1] / 2 + 1; // if (dita[i] <= 1) { // dita[i] = 1; // } // } //} return 0; } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20221005/9e4e75d3fa6d4b6abd4f06ca6a74ee34.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20221005/2a0ec67af08f4efbbf2859406453ebc1.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]: /images/20221005/70a17fb57a414bcabefcb033f3e5cc81.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]: /images/20221005/c6e5d4b59821439888a9603ed6d77aa8.png
相关 [排序算法] 常见的排序算法 前言 1.冒泡排序 2.选择排序 3.插入排序 4希尔排序 5.归并排序 6.快速排序 前言 在实际需求中，我们可能要 雨点打透心脏的1/2处/ 2023年09月29日 14:29/ 0 赞/ 225 阅读
相关 常见基本排序算法 文章目录 直接插入排序 希尔排序 归并排序 快速排序 应用 直接插入排序 一个一个逐步插入 ![在这里插入图片描述][water 不念不忘少年蓝@/ 2022年10月08日 14:21/ 0 赞/ 118 阅读
相关 常见排序算法 注：点进链接查看算法具体实现！！！ -------------------- 插入排序 [直接插入排序][Link 1] [希尔排序][Link 2] - 怼烎@/ 2022年06月16日 09:10/ 0 赞/ 191 阅读
相关 基本排序算法 1.冒泡排序： 排序基本思想： 一个一个的比较，将最大或者最小的数冒到最后面； 是稳定算法 算法时间复杂度：大于 n ^ 2; // 默认从小到大 小灰灰/ 2022年05月31日 08:56/ 0 赞/ 135 阅读
相关 常见排序算法 常见排序算法 排序问题作为算法基础的重要组成部分，代码实现方式多种多样，但其原理是基本一致的。常见的排序算法有： ①. 冒泡排序 ②. 选择排序 ③. 插入排序 偏执的太偏执、/ 2022年05月16日 07:28/ 0 赞/ 264 阅读
相关 常见排序算法 今天实在不想刷笔试题就把常见的排序手敲了一遍 -------------------- 1.选择排序 class ChoiceSort<T extends 约定不等于承诺〃/ 2022年01月15日 13:35/ 0 赞/ 279 阅读
相关 常见排序算法 稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。（即原本a在b 墨蓝/ 2022年01月06日 03:01/ 0 赞/ 301 阅读
雨点打透心脏的1/2处
不念不忘少年蓝@
怼烎@
小灰灰
还没有评论，来说两句吧...