云南龙网

  1. 首页 > 云知道 > >

合并排序实验报告总结 合并排序c语言算法代码( 二 )

云知道合并


第一层循环：遍历待比较的所有数组元素
第二层循环：将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较 。如果：selected > ordered，那么将二者交换 。
算法代码：
void print(int a[], int n ,int i){ cout< for(int j= 0; j<8; j){ cout< } cout<} void InsertSort(int a[], int n){ for(int i= 1; i if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入 。小于的话，移动有序表后插入 int j= i-1; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-1]; //先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j 1] = a[j]; j--; //元素后移 } a[j 1] = x; //插入到正确位置 } print(a,n,i); //打印每趟排序的结果 }
}
int main{ int a[8] = {3,1,5,7,2,4,9,6}; InsertSort(a,8); print(a,8,8);}二、希尔排序（Shell’ s Sort）
算法思想:
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本 。但希尔排序是非稳定排序算法 。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序 。
算法步骤：
1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列个数k，对序列进行k 趟排序；
3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序 。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度 。
算法代码:
void print(int a[], int n ,int i){ cout< for(int j= 0; j<8; j){ cout< } cout<}/** * 直接插入排序的一般形式 * * @param int dk 缩小增量，如果是直接插入排序，dk=1 * */
void ShellInsertSort(int a[], int n, int dk){ for(int i= dk; i if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插入 。小于的话，移动有序表后插入 int j = i-dk; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-dk]; //首先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j dk] = a[j]; j -= dk; //元素后移 } a[j dk] = x; //插入到正确位置 } print(a, n,i ); }
}
// 先按增量d（n/2,n为要排序数的个数进行希尔排序void shellSort(int a[], int n){
int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; }}int main{ int a[8] = {3,1,5,7,2,4,9,6}; //ShellInsertSort(a,8,1); //直接插入排序 shellSort(a,8); //希尔插入排序 print(a,8,8);}三、简单选择排序（Selection Sort）
算法思想：
简单选择排序的实现思想：比较 交换

  1. 从待排序序列中，找到关键字最小的元素；
  2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
  3. 从余下的 N – 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束 。因此我们可以发现，简单选择排序也是通过两层循环实现 。第一层循环：依次遍历序列当中的每一个元素 第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换 。

    推荐阅读


上一篇：详解proteus仿真步骤 keil5仿真调试教程

下一篇：天将雄狮什么日的人,《天将雄师》评测