排序 归并排序 分配排序

归并排序

         基本思想:将两个或两个以上的有序子序列“归并”为一个有序子序列。在内部排序中,通常采用的是2-路归并排序,即将两个位置相邻的有序子序列“归并”为一个有序序列。类似于快排,其使用的也是分治的策略。

二路归并排序

基本思想:将有n个记录的原始序列看做n个有序子序列,每个子序列的长度为1,然后从第1个子序列开始,把相邻的子序列两两合并,得到n/2个长度为2或1的子序列(当子序列的个数为奇数是,最后一组合并得到的序列长度为1),我们把这一过程称为一次归并排序,对一次归并排序的n/2个子序列采用上述方法继续顺序成成对归并,如此重复,当最后得到长度为n的一个子序列时,该子序列便是原始序列归并后的有序序列。

过程如图所示:

第一趟:将列表中的11个元素看成11个有序的序列,每个子序列的长度为1,然后两两归并,得到5个长度为2和1个长度为1的有序子序列。

第二趟:将6个有序子序列两两合并,得到2个长度为4和1个长度为3的有序子序列。

第三趟:将2个长度为4的有序子序列归并,得到第3趟归并结果。

第四趟:将长度为8有序子序列和长度为3的有序子序列归并,得到第4趟归并结果,是长度为11的一个有序子序列。

时间复杂度:O(nlog2n)

代码实现:

/// <summary>

/// 归并排序

/// </summary>

/// <paramname="arr"></param>

public static void mergeSort(ref int[]arr)

{

int k = 1;

while (k < arr.Length)

{

arr=merge(arr, k);

k *= 2;

}

}

private static int[] merge(int[]arr,int len)

{

int m = 0;//临时顺序表的起始位置

int l1 = 0;//第一个有序表的起始位置

int h1;//第一个有序表的结束位置

int h2,l2,i = 0,j = 0;

int[] tarr = new int[arr.Length];

//归并处理

while (l1 + len < arr.Length)

{

l2 = l1 + len;//第二个有序序列的起始位置

h1 = l2 - 1;//第一个序列的结束位置

//第二个有序表的结束位置

h2 = l2 + len - 1 <arr.Length ? l2 + len - 1 : arr.Length - 1;

j = l2; i = l1;

//两个有序表中的记录没有排序完

while (i <= h1 && j<= h2)

{

if (arr[i] <= arr[j])

{

tarr[m++] = arr[i++];

}

else

{

tarr[m++] = arr[j++];

}

}

//第一个有序表中还有记录没有排序完

while (i <= h1)

{

tarr[m++] = arr[i++];

}

//第二个有序表中还有记录没有排序完

while (j <= h2)

{

tarr[m++] = arr[j++];

}

l1 = h2 + 1;

}

i = l1;

//原顺序表中还有记录没有排序完

while (i < arr.Length)

{

tarr[m++] = arr[i++];

}

return tarr;

}

分配排序

         分配排序的基本思想:排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。他们的时间复杂度可达到线性阶:O(n)

(1)      最高位优先法(MSD法):先按最主位关键码进行排序,分成不同的组,再按次主位关键码进行排序,进行细化,依次类推,然后将各个子序列连接起来,便得到一个有序序列。

(2)      最次位优先法(LSD法):与MSD方向相反。

时间: 09-28

排序 归并排序 分配排序的相关文章

常见的排序算法(四)( 归并排序,计数排序 , 基数排序)

 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. (如果读者不太了解什么叫分治法,可以去看看<算法导论>第一二章.) 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第

九种经典排序算法详解(冒泡排序,插入排序,选择排序,快速排序,归并排序,堆排序,计数排序,桶排序,基数排序)

综述 最近复习了各种排序算法,记录了一下学习总结和心得,希望对大家能有所帮助.本文介绍了冒泡排序.插入排序.选择排序.快速排序.归并排序.堆排序.计数排序.桶排序.基数排序9种经典的排序算法.针对每种排序算法分析了算法的主要思路,每个算法都附上了伪代码和C++实现. 算法分类 原地排序(in-place):没有使用辅助数据结构来存储中间结果的排序**算法. 非原地排序(not-in-place / out-of-place):使用了辅助数据结构来存储中间结果的排序算法 稳定排序:数列值(key)

冒泡排序,快速排序,归并排序,插入排序,希尔排序,堆排序,计数排序,桶排序,基数排序

选择排序,冒泡排序,快速排序,归并排序,插入排序,希尔排序,计数排序,桶排序,基数排序 以上是一些常用的排序算法. 选择排序 for(int i = 0; i < n; i++) { int minval = a[i]; int minid = i; for (int j = i+1; j < n; j++) { if (a[j] < minval) { minid = j; minval = a[j]; } } swap(a[i], a[minid]); } 最简单的就是选择排序,就是

插入排序 | 冒泡排序 | 希尔排序 | 堆排序 | 快速排序 | 选择排序 | 归并排序

以下是最近学习各种算法的代码实现: #include <stdlib.h> #include <stdio.h> #include <time.h> #include <limits.h> typedef int EleType; typedef int (*CompFunc)(void *,void *); int IntComp(void * a,void *b) { if(*(int *)a > *(int *)b) return 1; if(*

JavaScript排序算法(希尔排序、快速排序、归并排序)

以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

归并排序-八大排序三大查找汇总(7)

基本思想 归并排序简单的说就是递归后合并,该算法是分治法(Divide and Conquer)的一个典型应用. 基本思想为:将待排序序列R[0...n-1]看成是n个长度为1的有序序列,两两有序表成对归并,得到n/2个长度为2的有序表:将这些有序序列再次归并,如此反复进行下去,最后得到一个长度为n的有序序列. 综上可知: 归并排序其实要做两件事: (1)“分解”——将序列每次折半划分. (2)“合并”——将划分后的序列段两两合并后排序. 性能 排序类别 排序方法 时间复杂度 空间复杂度 稳定性

插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LST基数排序——C++实现

首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T temp = a; a = b; b = temp; } //插入排序:时间复杂度o(n^2) template<

如何给10^7个数据量的磁盘文件进行排序--归并排序

接上面的题目,假若待排序的数据有重复的呢?这里采用的是归并排序. 1.算法分析:     1.稳定性:归并排序是一种稳定的排序.    2.存储结构要求:可用顺序存储结构.也易于在链表上实现.    3.时间复杂度: 对长度为n的文件,需进行lgn趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)..    4.空间复杂度:需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序. 2.总结 与快速排序相

排序算法(七)非比较排序:计数排序、基数排序、桶排序

前面讲的是比较排序算法,主要有冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等. 非比较排序算法:计数排序,基数排序,桶排序.在一定条件下,它们的时间复杂度可以达到O(n). 一,计数排序(Counting Sort) (1)算法简介 计数排序(Counting sort)是一种稳定的排序算法.计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数.然后根据数组C来将A中的元素排到正确的位置.它只能对整数进行排序. (2)算法描述和实现 得到待排序数的范围(在