1:插入排序 - 直接插入排序
基本思想:
将一个数字插入到已排好序的有序表当中,从而得到一个新的更大的有序表, 即将序列的第一个记录看成是一个有序的子序列, 然后将从第二个记录插入, 直至整个序列都有序为止.
如果发现一个和插入元素相等的,我们既可以将元素按照原来的顺序摆放得到稳定排序, 也可以改变位置得到不稳定排序.
算法实现: 效率 O(n^2)
void print(int a[], int n ,int i){ cout<<<":"; for(int j= 0; j<8; j++){ cout< <<" "; } cout<
2:插入排序 -希尔排序(Shell's Sort)
希尔排序于1959年由D.L.Shell提出,相对于直接排序有较大的改进.希尔排序又称为缩小量排序.
基本思想:
将整个待排序的记录序列分割成若干子序列分别进行直接插入排序, 待整个序列中的记录基本有序的时候, 再对全体记录进行依次直接插入排序.
操作方法:
1:选择一个增量序列t1,t2,t3,...,tk,其中ti>tj, tk=1;
2:按增量序列的个数k, 对序列进行k趟排序.
3:每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各个子表进行直接插入排序, 仅增量因子位1 时, 整个序列作为一个表来处理, 表长度位整个序列的长度.
算法实现:
void shellsort(int a[], int n){ int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) //gap4 for (i = gap; i < n; i++) //从4开始增加 for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) // swap(a[j], a[j + gap]);}
3:选择排序 - 简单选择排序(Simple Selection Sort)
基本思想:
在要排序的一组数中,选出最小(最大也可以)的数组,和第一个数进行交换, 在剩下的数中选出第二小的和第二个数字进行交换,以此类推.
操作方法:
略
实现算法:
void SelectionSort(int a[],int n){ int pos = 0,minPos = INT_MAX,selPos = 0,i;// 从 0 点开始 for(;selPos
4:选择排序 - 堆排序
堆排序是一种树型选择排序,是对直接选择排序的有效改进.
基本思想:
具有N个元素的序列(k1,k2,k3.......kn),当且仅当满足
时称为堆,由堆的定义可以看出,堆顶元素(即第一个元素)必须为最小项(小顶堆)
若用一维数组储存一个堆,则堆对应一颗完全二叉树,且所有非叶结点的值均不大于其子女的值.
(a) 大顶堆序列:(96,83,27,38,11,09)
(b) 小顶堆序列:(12,36,24,85,47,30,53,91)
初始时要把排序的n个数的序列看做是一颗顺序储存的二叉树(一维数组储存的二叉树), 调整他们的储存顺序,使之成为一个堆, 讲堆顶元素输出,得到n个元素中的最小或者最大的元素, 这是堆的根节点的的数量最小或者最大,然后堆前面的(n-1)个节点重新调整使之称为新的堆,输出对应元素,得带n个元素中次大或者次小的元素. 以此类推,直到只有两个节点的堆.
因此我们就有了另一个问题(有点像,我觉得这个问题正则表达式可以解决,所以我现在有两个问题了.):
1: 如何将n个待排序的数字建成堆.
2: 输出堆顶元素之后, 怎样调整剩余的n-1个元素, 使其成为一个新堆 .
1) 首先讨论第二个问题: 输出堆顶元素之后, 对剩余的m-1 个元素,讲话堆低元素送入堆顶, 堆被破坏, 其原因是根节点不满足堆得性质.
2) 将根节点和左右子树中较小元素进行交换.
3) 若与左子树交换: 如果左子树的堆被破坏, 即左子树的根节点不满足堆的性质, 则重复方法2.
4) 若与右子树交换: 如果右子树的堆被破坏, 即右子树的根节点不满足堆得性质, 则重复方法2.
5) 继续对不满足堆性质的子树进行上述操作, 直到叶子节点, 堆被建成.
称这个自根节点到叶子节点的调整过程称为筛选. 如图所示:
现在讨论如何将一些数字建立为一个初始化的堆.
1) n个节点的完全二叉树, 最后一个节点是第[n/2] 个节点的子树.
2) 筛选从筛选从第[n/2] 个节点的子树开始, 该子树成为堆.
3) 之后向前依次对各个节点为根的子树进行筛选使之称为堆, 直至根节点.
如图所示为 建堆过程: 无序序列: (49，38，65，97，76，13，27，49)
从算法描述上来看, 堆排序需要两个过程 一: 建立堆 , 二 : 堆顶和堆的最后一个元素交换位置. 所以堆排序需要两个函数, 一是堆的渗透函数 , 二是 饭后服调用渗透函数实现排序的函数 .
算法的实现:
#include#include #include #include #include #include #include #include #include #include #include #include #include
5: 交换排序 - 冒泡排序(Bubble Sort)
基本思想:
在要排序的一组数中,对当前还未排好序的范围内的全部数, 自上而下堆相邻的相隔数进行一次比较和调整让最大的数下沉, 小的数上升.
void bubbleSort(int a[], int n){ for(int i =0 ; i< n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp; } } }} 6: 交换排序 - 快速排序(Quick Sort)
基本思想:
1) 选择一个基准元素, 通常选择第一个元素,或者最后一个元素.
2) 通过一趟排序将待排序列分为独立的两部分, 其中一部分的记录的元素值 均比基准元素小 . 而另一部分记录的元素值 比基准值大
3) 此时基准元素在其排好序之后的正确位置.
4) 然后堆这两部分记录用同样的方法进行排序, 直至序列有序.
#include#include #include #include #include #include #include #include #include #include #include #include #include
7: 归并排序 (Merge Sort)
基本思想:
归并排序是将两个(或者两个以上)的有序表合成一个新的有序表, 即将待排序的序列分成若干个子序列, 每个子序列是有序的. 然后再把有序子序列合并成整体有序序列.
#include#include #include #include #include #include #include #include #include #include #include #include #include