以下是小编为大家整理的数据结构――归并排序，本文共7篇，欢迎阅读与收藏。本文原稿由网友“姚琛”提供。
篇1：数据结构――归并排序
1、算法思想：
[数据结构]中要合并两个有序线性表时，每次取出头部较小的一个加入合并的表后面，再读其下一个，最后剩下的那个线性表中的所有元素全部加速合并表后面，
2、利用这种思想对数据排序
归：利用递归的思想，将一个数组、链表一直均等分割下去，直到每个组只剩下一个为止；
并：将之前分割后的数组两两之间合并，结果再两两合并…一直合并下去，直到只剩下一个数组。
3、源代码之递归实现
#include
#include “list_sort.h”
//merge a segment of an array, minimum at the first
void merge1（ int *arr, int first, int mid, int last, char *temp ）
{
int i = first;
int j = mid + 1;
int k = 0;
while （ i <= mid && j <= last ）
{
if （ arr[i] < arr[j]）
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while （ i <= mid ）
temp[k++] = arr[i++];
while （ j <= last ）
temp[k++] = arr[j++];
for （ k = first; k <= last; k++ ）
arr[k] = temp[k - first];
}
//use temp to save memory
void mergeSort1（ int *arr, int first, int last, char *temp ）
{
if （ first < last ）
{
int mid = （first + last） / 2;
mergeSort1 （ arr, first, mid, temp ）；
mergeSort1 （ arr, mid + 1, last, temp ）；
merge1 （ arr, first, mid, last, temp ）；
}
}
void merge_Array_Sort1（int *arr, int len）
{
char temp[len + 1];
mergeSort1（arr, 0, len - 1, temp）；
}
4、递归实现的时间复杂度和空间复杂度分析
整个归并排序需要将数组拆分log2N次，即调用了log2N次递归函数。
每次递归都对N个数据进行了操作。所以，时间复杂度为：O（N*logN）
由于栈有log2N层，每一层总共要维护N个数据，所以空间复杂度也是：O（N*logN）
这样看来，其时间复杂度、空间复杂度并不高。
递归算法易于读懂、实现起来较为容易，但是其空间复杂度仍可进一步下降。所以我再用非递归的方法实现了归并排序。
5、非递归的归并排序
#include
#include
#include “list_sort.h”
void merge2（ int *arr1, int *arr2, int first, int mid, int last ）
{
int i = first;
int j = mid + 1;
int k = first;
while （ i <= mid && j <= last ）
{
if （ arr1[i] < arr1[j]）
arr2[k++] = arr1[i++];
else
arr2[k++] = arr1[j++];
}
while （ i <= mid ）
arr2[k++] = arr1[i++];
while （ j <= last ）
arr2[k++] = arr1[j++];
}
//将arr1（长度为len），每段间隔为s,两两合并到arr2
void mergeSort2（ int *arr1, int *arr2, int len, int s ）
{
int i = 0;
int j = 0;
int first;
int mid;
int last;
//所有长度为s的分段两两合并
int times = len / （2 * s）；
for （ i = 0; i < times; i++ ）
{
first = 2 * i * s;
mid = first + s - 1;
last = first + 2 * s - 1;
merge2（ arr1, arr2, first, mid, last）；
}
//倒数第二段长度为s,最后一段长度大于0、小于s
int remain = len % （s * 2）；
first = 2 * times * s;
if （ remain >s ）
{
mid = first + s - 1;
last = len - 1;
merge2（ arr1, arr2, first, mid, last ）；
}
else
for（ j = first; j < len; j++ ）
arr2[j] = arr1[j];
}
void merge_Array_Sort2（ int *arr, int len ）
{
int i;
int *temp = （int *）malloc（sizeof（int） * len）；
int s = 1;
while （s < len）
{
mergeSort2 （ arr, temp, len, s ）；
s *= 2;
for （i = 0; i < len; i++）
{
arr[i] = temp[i];
}
}
}
篇2：归并排序和快速排序的浅析
次记录下归并排序和快速排序，以及短作业优先调度的算法，咋一看，其实，前后并没有联系，确实，实际也是没有啥联系的，只是为了将要讲的东西都凑到一起，然后做个总结，仅此而已，先讲下归并排序吧，还是沿袭上一次的一个归纳的方式来给出。
归并排序：就是将一堆数从一小撮，归到一大撮，最后变成有序的数列。简而言之就是这样的一个现象，但具体是怎样表现的呢？最基本的一小撮可以理解为只有两个数，那么这两个数的大小是可以比较得出的，最终两个数的先后排序肯定是很容易的，这个我们很容易理解，基于这样一个思路，我们可以知道最后归并的时候，就是一整串数了，而这些数都是有序的，还是一样，我们来看它的核心部分算法，就是比较然后归并，这样一个核心部分，首先应该知道，归并肯定是有两撮数，那么我们需要做的就是将这两撮数归成一撮数，而且是有序的，在这个过程中，我们借助了中间数组的方法，来存放这组中间数，最后再将它们放回原先的数组。记住这个算法的核心部分代码，记住三个while，第一个是两组排序然后合并，顺利的情况下只需要运行这个while，第二三个while是将剩余的左边或者右边的数存进中间数组，最后复制。它的时间复杂度是O(nlog2n)核心代码如下：
Int temp=left;
Int tempArr=new int[arr.length];//定义中间数组，用作临时缓冲区
Int mid=center+1;
//从这里可以看出将原数组分为两部分，一部分是从left到center，一部分是从mid到right。
Int base=left;//后来将中间数组的数复制回原来的数组用的下标计数
While(left<=center&&mid<=right)//要求两边比较时，下标不能超过界限，这是最基本的
{
If(arr[left]<=arr[mid])//进行两边下标的比较，小的放中间数组，知道两边下标有一个超过
{
tempArr[temp++]=data[left++];
}
else
{
tempArr[temp++]=data[mid++];
}
}
While(left<=center)//可能右边数组都比左边大，那么左边剩下的直接插入到中间数组中
{
tempArr[temp++]=data[left++];
}
While(mid<=right)//同理，左边数组都比右边小，那么右边剩下的数直接插入到中间数组中
{
tempArr[temp++]=data[mid++];
}
While(base<=right)//将中间数组复制回原来的数组。
{
Data[base]=tempArr[base++];
}
第二部分的代码，虽不归结于核心，但是还是有递归的思想在里面：
将原始数组递归，最后归并：
Public void sort(int[] data,int left,int right)
{
If(left
{
Center=(left+right)/2;
Sort(data,left,center);
Sort(data,center+1,right);
Merge(data,letf,center,right);
}
}
接下来讲下，最经典的快速排序，它是所有内排序中最快的一种，因此得名，快速排序的核心步骤是它从两边出发，比较到合适的赋值后，另一边开始比较，最后两个游标相等时，排序结束，将枢纽赋值给这两个游标对应的位置，
以此类推，到最底部，就剩下两个数的比较了。一般快速排序都会有一个枢纽的选择，一般是第一个数，然后两边开始和这个数进行比较，大的放在右边，小的放在左边，左边和右边指的是当时游标对应的位置，而这个枢纽，我们可以假想它被放在一个特殊的地方，而它的位置是空的，最后这个空的位置再有枢纽来填写，这样，我们可以来分解下，先看核心代码：
int rule=arr[0];
int i=low;
int j=high;
while(low
{
while(low
{
Right–;
}//这个循环主要是为了从后面往前来和中枢比较，如果发现比其小，那么进行下面的操作
If(low
{
Arr[low]=arr[right];
Low++;
}//发现后面的数比中枢小，那么将前面的游标对应的数赋值为该数，并将游标向后移
while(low
{
Low++;
}//这个循环是从前向后和中枢比较，大的进行接下来的操作
If(low
{
Arr[right]=arr[low];
Right–;
}
到这里为一个循环，即前面赋值一个数，后面赋值一个数，这是一次循环，如果low还是小right，那么继续这种循环
}
Arr[low]=rule;
当然，还包括递归算法：
Sort(data,i,low-1);
Sort(data,low+1,j);
篇3：归并排序算法的JAVA实现Java
package Utils.Sort; /** * MI LY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'“>归并排序，要求待排序的数组必须实现 Comparable 接口 */ public class MergeSort implements SortStrategy { private Compa
package Utils.Sort;
/**
*MILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'”>归并排序，要求待排序的数组必须实现Comparable接口
*/
public class MergeSort implements SortStrategy
{private Comparable[] bridge;
/**
*利用归并排序算法对数组obj进行排序
*/
public void sort(Comparable[] obj)
{if (obj == null)
{throw new NullPointerException(“The param can not be null!”);
}
bridge = new Comparable[obj.length];//初始化中间数组mergeSort(obj, 0, obj.length - 1);//归并排序
bridge = null;
}
/***将下标从left到right的数组进行归并排序
*@param obj要排序的数组的句柄
*@param left要排序的数组的第一个元素下标
*@param right要排序的数组的最后一个元素的下标
*/
private void mergeSort(Comparable[] obj, int left, int right)
{if (left < right)
{int center = (left + right)/2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
/**
*将两个对象数组进行归并，并使归并后为升序，
归并排序算法的JAVA实现Java
，
归并前两个数组分别有序
*@param obj对象数组的句柄
*@param left左数组的第一个元素的下标
*@param center左数组的最后一个元素的下标
*@param right右数组的最后一个元素的下标
*/
private void merge(Comparable[] obj, int left, int center, int right)
{int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right)
{//从两个数组中取出小的放入中间数组
if (obj[left].compareTo(obj[mid]) <= 0)
{bridge[third++] = obj[left++];
}else
bridge[third++] = obj[mid++];
}
//剩余部分依次置入中间数组while (mid <= right)
{bridge[third++] = obj[mid++];
}
while (left <= center){bridge[third++] = obj[left++];
}
//将中间数组的内容拷贝回原数组copy(obj, tmp, right);
}
/***将中间数组bridge中的内容拷贝到原数组中
*@param obj原数组的句柄
*@param left要拷贝的第一个元素的下标
*@param right要拷贝的最后一个元素的下标
*/
private void copy(Comparable[] obj, int left, int right)
{while (left <= right)
{obj[left] = bridge[left];
left++;
}}
}
原文转自：www.ltesting.net
篇4：C语言二路归并排序算法
写了个二路归并的归并排序小代码，直接贴上来
/*
file:quick.cpp
author:www.5dkx.com
*/
#include
using namespace std;
void Merge(int a[],int low,int mid,int high,int b[]);
void MSort(int a[],int low,int high,int b[]);
void main
{
int a[]={4,5,9,10,51,6,46,36,6,56,67,45,36};
int b[13];
MSort(a,0,12,b);
for(int i=0;i<13;i++)
cout<
cout<
for(int j=0;j<13;j++)
cout<
cout<
}
void Merge(int a[],int low,int mid,int high,int b[])
{
int i=low,j=mid+1,k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
while(i<=mid)
{
a[k]=a[i];
k++;
i++;
}
while(j<=high)
{
a[k]=a[j];
k++;j++;
}
}
void MSort(int a[],int low,int high,int b[])
{
if(low==high)
b[low]=a[low];
else
{
int mid=(low+high)/2;
MSort(a,low,mid,b);
MSort(a,mid+1,high,b);
Merge(a,low,mid,high,b);
}
}
篇5：疯狂的Java算法――插入排序，归并排序以及并行归并排序
从古至今的难题
在IT届有一道百算不厌其烦的题，俗称排序，不管是你参加BAT等高端笔试，亦或是藏匿于街头小巷的草根笔试，都会经常见到这样一道百年难得一解的问题。
今天LZ有幸与各位分享一下算法届的草根明星，排序届的领衔大神——插入排序以及归并排序。最后，在头脑风暴下，LZ又有幸认识了一位新朋友，名叫并行归并排序。接下来，咱们就一一认识一下，并且在最后来一次“算林大会”吧。
插入排序简介
插入排序，算林称最亲民的排序算法，插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素，并且将每一个循环到的元素插入到相应的位置，从而实现排序的目的。
插入排序的代码展示
使用Java代码描述插入排序，可以用以下的代码。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class InsertSort {
public static void sort(int[] numbers){
for (int i = 1; i < numbers.length; i++) {
int currentNumber = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] >currentNumber) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = currentNumber;
}
}
}
复制代码
这个算法从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。
插入排序理解起来比较简单，因此LZ就不过多的解释它的实现原理了，尚未理解的猿友可以自行研究。
插入排序的性能分析
接下来，咱们来简单分析一下插入排序的性能。首先，插入排序当中有两个循环，假设数组的大小为n，则第一个循环是n－1次，第二个while循环在最坏的情况下是1到n－1次。因此插入排序的时间复杂度大约为如下形式。
1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）
时间复杂度为输入规模的2次函数，可见插入排序的时间复杂度是比较高的。这是原理上的简单分析，最后在“算林大会”中，各位可以清楚的看到插入排序随着输入规模的增长，时间会指数倍的上升。
归并排序简介
归并排序，算林届的新秀，引领着分治法的潮流。归并排序将排序问题拆分，比如分成两个较小的数组，然后对拆分后的数组分别进行排序，最后再将排序后的较小数组进行合并。
这种思想是一种算法设计的思想，很多问题都可以采用这种方式解决。映射到编程领域，其实就是递归的思想。因此在归并排序的算法中，将会出现递归调用。
归并排序的代码展示
归并排序主要由两个方法组成，一个是用于合并两个已经排序的数组的方法，一个则是递归方法，用于将问题无限拆分。接下来咱们一起看看归并排序的Java代码展示，如下所示。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeSort {
public static void sort(int[] numbers){
sort(numbers, 0, numbers.length);
}
public static void sort(int[] numbers,int pos,int end){
if ((end - pos) >1) {
int ffset = (end + pos) / 2;
sort(numbers, pos, offset);
sort(numbers, offset, end);
merge(numbers, pos, offset, end);
}
}
public static void merge(int[] numbers,int pos,int offset,int end){
int[] array1 = new int[offset - pos];
int[] array2 = new int[end - offset];
System.arraycopy(numbers, pos, array1, 0, array1.length);
System.arraycopy(numbers, offset, array2, 0, array2.length);
for (int i = pos,j=0,k=0; i < end ; i++) {
if (j == array1.length) {
System.arraycopy(array2, k, numbers, i, array2.length - k);
break;
}
if (k == array2.length) {
System.arraycopy(array1, j, numbers, i, array1.length - j);
break;
}
if (array1[j] <= array2[k]) {
numbers[i] = array1[j++];
} else {
numbers[i] = array2[k++];
}
}
}
}
可以看到，归并排序将一个长度为n的数组平均分为两个n/2的数组分别进行处理，因此，在sort方法中又调用了两次sort方法自身。当数组大小为1时，则认为该数组为已经为排好序的数组。因此在sort方法中，需要end与pos相差大于2时，才需要进一步拆分，这也是递归的终止条件。
此外，在代码中，使用了Java提供的arraycory函数进行数组复制，这种直接复制内存区域的方式，将会比循环赋值的方式速度更快。有些算法实现会给merge方法中的两个临时数组设置哨兵，目的是为了防止merge中for循环的前两个if判断。为了方便理解，LZ这里没有设置哨兵，当某一个数组的元素消耗完时，将直接使用arraycopy方法把另外一个数组copy到numbers当中。
归并排序的性能分析
与插入排序一样，咱们来简单分析一下归并排序的时间复杂度。咱们假设数组的大小为n，sort方法的时间复杂度为f（end－pos）。简单的分析merge方法的复杂度，不难发现为（end－pos）＊2，这个结果的前提是咱们认为arraycopy方法的复杂度为length参数。
基于以上的假设，由于end－pos的初始值为n，因此归并排序的复杂度大约为如下形式。
2＊f（n/2） ＋ 2＊n ＝ 2＊（2＊f（n/4）＋2＊（n/2）） ＋ 2＊n＝4＊f（n/4） ＋ 2＊n ＋ 2＊n ＝ n ＊f（1） ＋ 2＊n ＋...＋2＊n
其中f（1）的时间复杂度为常量，假设f（1）＝c，而2＊n将有log2n个。因此咱们得到归并排序的最终时间复杂度为如下形式。
cn ＋ 2n＊log2n ＝ O（n＊log2n）
归并排序的时间复杂度与插入排序相比，已经降低了很多，这一点在数组的输入规模较大时将会非常明显，因为log函数的增加速度将远远低于n的增加速度。
并行归并排序简介
并行归并排序是LZ在学习归并排序时意淫出来的，最近LZ正在研究Java的并发编程，恰好归并排序的子问题有一定的并行度与独立性，因此LZ版的并发归并排序就这样诞生了。事后，LZ也人肉过并行归并排序这个家伙，发现早已众所周知，不过在不知道的情况下自己能够想到是不是也应该窃喜一下呢。
并行归并排序与普通的归并排序没有多大区别，只是利用现在计算机多核的优势，在有可能的情况下，让两个或多个子问题的处理一起进行。这样一来，在效率上，并行归并排序将会比归并排序更胜一筹。
并行归并排序的代码展示
并行归并排序主要对sort方法进行了修改，基础的merge方法与普通的归并排序是一样的。因此在进行并行归并排序时，引用了归并排序的一些方法，具体的代码如下所示。
package algorithm;
import java.util.concurrent.CountDownLatch;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeParallelSort {
private static final int maxAsynDepth = (int)(Math.log(Runtime.getRuntime().availableProcessors())/Math.log(2));
public static void sort(int[] numbers) {
sort(numbers, maxAsynDepth);
}
public static void sort(int[] numbers,Integer asynDepth) {
sortParallel(numbers, 0, numbers.length, asynDepth >maxAsynDepth ? maxAsynDepth : asynDepth, 1);
}
public static void sortParallel(final int[] numbers,final int pos,final int end,final int asynDepth,final int depth){
if ((end - pos) >1) {
final CountDownLatch mergeSignal = new CountDownLatch(2);
final int ffset = (end + pos) / 2;
Thread thread1 = new SortThread(depth, asynDepth, numbers, mergeSignal, pos, offset);
Thread thread2 = new SortThread(depth, asynDepth, numbers, mergeSignal, offset, end);
thread1.start();
thread2.start();
try {
mergeSignal.await();
} catch (InterruptedException e) {}
MergeSort.merge(numbers, pos, offset, end);
}
}
static class SortThread extends Thread {
private int depth;
private int asynDepth;
private int[] numbers;
private CountDownLatch mergeSignal;
private int pos;
private int end;
/**
* @param depth
* @param asynDepth
* @param numbers
* @param mergeSignal
* @param pos
* @param end
*/
public SortThread(int depth, int asynDepth, int[] numbers, CountDownLatch mergeSignal, int pos, int end) {
super();
this.depth = depth;
this.asynDepth = asynDepth;
this.numbers = numbers;
this.mergeSignal = mergeSignal;
this.pos = pos;
this.end = end;
}
@Override
public void run() {
if (depth < asynDepth) {
sortParallel(numbers,pos,end,asynDepth,(depth + 1));
} else {
MergeSort.sort(numbers, pos, end);
}
mergeSignal.countDown();
}
}
}
在这段代码中，有几点是比较特殊的，LZ简单的说明一下，
1，分解后的问题采用了并行的方式处理，并且咱们设定了一个参数asynDepth去控制并行的深度，通常情况下，深度为(log2CPU核数)即可。
2，当子问题不进行并行处理时，并行归并排序调用了普通归并排序的方法，比如MergeSort.sort和MergeSort.merge。
3，因为合并操作依赖于两个子问题的完成，因此咱们设定了一个合并信号（mergeSignal），当信号发出时，才进行合并操作。
并行归并排序在原理上与普通的归并排序是一样的，只是对于子问题的处理采用了一定程度上的并行，因此如果猿友们理解归并排序，那么并行归并排序并不难理解。
并行归并排序的性能分析
并行归并排序只是将普通归并排序中一些可并行的操作进行了并行处理，因此在总体的时间复杂度上并没有质的变化，都是O（n＊log2n）。
由于并行归并排序将某些排序操作并行操作，因此在性能上一定是快于普通归并排序算法的。不过这也不是一定的，当数组规模太小时，并行带来的性能提高可能会小于线程创建和销毁的开销，此时并行归并排序的性能可能会低于普通归并排序。
算林大会
接下来，就是一周一度的算林大会了，本次算林大会主要由以上三种算法参加，胜者将会成为本周度最受欢迎算法。接下来是算林大会的代码，请各位猿友过目。
package algorithm;
import java.io.File;
import java.lang.reflect.Method;
import java.util.Random;
/**
* @author zuoxiaolong
*
*/
public class SortTests {
public static void main(String[] args) {
testAllSortIsCorrect();
testComputeTime(“MergeParallelSort”, 40000, 5);
testComputeTime(“MergeSort”, 40000, 5);
testComputeTime(“InsertSort”, 400, 5);
}
public static void testAllSortIsCorrect() {
File classpath = new File(SortTests.class.getResource(“”).getFile());
File[] classesFiles = classpath.listFiles();
for (int i = 0; i < classesFiles.length; i++) {
if (classesFiles[i].getName().endsWith(“Sort.class”)) {
System.out.println(“---测试” + classesFiles[i].getName() + “是否有效---”);
testSortIsCorrect(classesFiles[i].getName().split(“\\\\.”)[0]);
}
}
}
public static void testSortIsCorrect(String className){
for (int i = 1; i < 50; i++) {
int[] numbers = getRandomIntegerArray(1000 * i);
invoke(numbers, className);
for (int j = 1; j < numbers.length; j++) {
if (numbers[j] < numbers[j-1]) {
throw new RuntimeException(className + “ sort is error because ” + numbers[j] + “<” + numbers[j-1]);
}
}
}
System.out.println(“---” + className + “经测试有效---”);
}
public static void testComputeTime(String className,int initNumber,int times,Object... arguments) {
long[] timeArray = new long[times];
for (int i = initNumber,j = 0; j < times; i = i * 10,j++) {
timeArray[j] = computeTime(i, className, arguments);
}
System.out.print(className + “时间增加比例：”);
for (int i = 1; i < timeArray.length ; i++) {
System.out.print((float)timeArray[i]/timeArray[i - 1]);
if (i < timeArray.length - 1) {
System.out.print(“,”);
}
}
System.out.println();
}
public static long computeTime(int length,String className,Object... arguments){
int[] numbers = getRandomIntegerArray(length);
long start = System.currentTimeMillis();
System.out.print(“开始计算长度为”+numbers.length+“方法为”+className+“参数为[”);
for (int i = 0; i < arguments.length; i++) {
System.out.print(arguments[i]);
if (i < arguments.length - 1) {
System.out.print(“,”);
}
}
System.out.print(“]，时间为”);
invoke(numbers, className, arguments);
long time = System.currentTimeMillis()-start;
System.out.println(time + “ms”);
return time;
}
public static int[] getRandomIntegerArray(int length){
int[] numbers = new int[length];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = new Random().nextInt(length);
}
return numbers;
}
public static void invoke(int[] numbers,String className,Object... arguments){
try {
Class
Class
parameterTypes[0] = int[].class;
for (int i = 0; i < arguments.length; i++) {
parameterTypes[i + 1] = arguments[i].getClass();
}
Method method = clazz.getDeclaredMethod(“sort”, parameterTypes);
Object[] parameters = new Object[parameterTypes.length];
parameters[0] = numbers;
for (int i = 0; i < arguments.length; i++) {
parameters[i + 1] = arguments[i];
}
method.invoke(null, parameters);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
以上代码testAllSortIsCorrect方法首先验证了三种算法的正确性，也就是说经过sort方法后，数组是否已经升序排列。需要一提的是，由于插入排序的性能太低，因此插入排序测试的最大规模为400万，而归并排序测试的最大规模为4亿。
接下来，大家就一起看看运行结果吧。以下是在LZ的mac pro上的运行结果，硬件配置为16G内存，4核i7。这种配置下，异步深度（asynDepth）默认为log24=2。
---测试InsertSort.class是否有效---
---InsertSort经测试有效---
---测试MergeParallelSort.class是否有效---
---MergeParallelSort经测试有效---
---测试MergeSort.class是否有效---
---MergeSort经测试有效---
开始计算长度为40000方法为MergeParallelSort参数为[]，时间为6ms
开始计算长度为400000方法为MergeParallelSort参数为[]，时间为44ms
开始计算长度为4000000方法为MergeParallelSort参数为[]，时间为390ms
开始计算长度为40000000方法为MergeParallelSort参数为[]，时间为3872ms
开始计算长度为400000000方法为MergeParallelSort参数为[]，时间为47168ms
MergeParallelSort时间增加比例：7.3333335,8.863636,9.9282055,12.181818
开始计算长度为40000方法为MergeSort参数为[]，时间为7ms
开始计算长度为400000方法为MergeSort参数为[]，时间为81ms
开始计算长度为4000000方法为MergeSort参数为[]，时间为839ms
开始计算长度为40000000方法为MergeSort参数为[]，时间为9517ms
开始计算长度为400000000方法为MergeSort参数为[]，时间为104760ms
MergeSort时间增加比例：11.571428,10.358025,11.343266,11.00767
开始计算长度为400方法为InsertSort参数为[]，时间为0ms
开始计算长度为4000方法为InsertSort参数为[]，时间为3ms
开始计算长度为40000方法为InsertSort参数为[]，时间为245ms
开始计算长度为400000方法为InsertSort参数为[]，时间为23509ms
开始计算长度为4000000方法为InsertSort参数为[]，时间为3309180ms
InsertSort时间增加比例：Infinity,81.666664,95.9551,140.76227
复制代码
首先可以看到，三种算法都是运行正确的。接下来，咱们可以对比一下三种算法的性能。
根据输出结果，规模为400万时的区别是最明显与直观的。并行归并排序仅需要390ms就完成了400万规模的排序，而普通的归并排序则需要839ms才可以，至于插入排序，简直是不可理喻，竟然需要300多万ms，大约50分钟。
咱们再来看三者的时间增长趋势。两种归并排序基本上与规模的增长趋势相似，每当规模增加10倍时，时间也基本上增加10倍，而插入排序则几乎是以100倍的速度在增加，刚好是数组规模增长速度的平方。其中的Infinity是因为当数组规模为400时，毫秒级别的计时为0ms，因此当除数为0时，结果就为Infinity。
当然了，这一次结果具有一定的随机性，猿友们可以在自己的电脑上多实验几次观察一下，不过插入排序的时间实在让人等的 。
篇6：[AS功能代码教程10] 数据结构排序算法
一、概论
对于数据的处理工作，排序是其最基本的运算之一，在当今的计算机系统中，花费在排序上的时间占系统CPU运行时间的很大比重。有资料表明，在一些商用计算机上，在排序上的CPU时间达到20％至60％。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。这些算法有力地发展、并充分地展示了算法设计的某些重要原则和高超技巧。因此，对于计算专业人员来说掌握排序算法是十分重要的。
二、排序算法简介
本次课程中我们将介绍六种排序方法：插入排序，选择排序，冒泡排序，希尔排序，快速排序及二路归并。
<1>直接选择排序(Selection Sort)：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。
<2>直接插入排序(Insertion Sort)：简单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。
<3>冒泡排序(Bubble Sort)：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。
<4>快速排序(Quick Sort)：是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为O(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。
<5>希尔排序(Shell Sort)：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为1，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。
<6>归并排序(Merge Sort)：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。
三、排序方法的选择
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要
(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；
但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。
这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法，但有一定的局限性：
1>关键字可分解。
2>记录的关键字位数较少，如果密集更好
3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
四、AS中排列数组
1.申请一个长度为n的数组A：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
A[i] = i;
}
trace(A);
2.将长度为n的数组打乱次序：
for (i=0; i < n; i++) {
var ran = int(Math.random*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}
trace(A)
3.将数组中的所有元素倒排序：
A.reverse();
trace(A)
五、AS实现排序算法：
在执行各各排序算法之前，已经默认存在一个乱序的数组 A[400]，默认代码：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
A[i] = i;
}
for (i=0; i < n; i++) {
var ran = int(Math.random()*n);
var temp = A[i];
A[i] = A[ran];
A[ran] = temp;
}
1.直接插入排序
for (i = 0; i < n; i++) {
var temp = A[i];
for (j = i; j >0 && temp < A[j - 1]; j--) {
A[j] = A[j - 1];
A[j - 1] = temp;
}
}
2.直接选择排序
for (i = 0; i < n - 1; i++) {
var s:Number = i;
for (j = s + 1; j < n; j++) {
if (A[j] < A[s]) {
s = j;
}
}
var temp = A[i];
A[i] = A[s];
A[s] = temp;
}
3.冒泡排序
for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
if (A[i] >A[j]) {
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
4.希尔排序
var increment = 6;
while (increment >1) {
increment = int(increment / 3 + 1);
Shellpass(increment);
}
function Shellpass(c) {
for (i = c; i < n; i++) {
if (A[i] < A[i - c]) {
var temp = A[i];
j = i - c;
do {
A[j + c] = A[j];
j = j - c;
} while (j >0 && temp < A[j]);
A[j + c] = temp;
}
}
}
5.快速排序
function QuickSort(A, low, hig) {
var i = low, j = hig;
var mid = A[int((low + hig) / 2)];
do {
while (A[i] < mid) {
i++;
}
while (A[j] >mid) {
j--;
}
if (i <= j) {
var temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
} while (i <= j);
if (low < j) {
arguments.callee(A,low,j);
}
if (i < hig) {
arguments.callee(A,i,hig);
}
}
QuickSort(A,0,n - 1);
6.二路归并
var B:Array = new Array(A.length);
for (k = 1; k < n; k *= 2) {
MergePass(k);
}
function MergePass(len) {
for (i = 0; i + 2 * len < n; i = i + 2 * len) {
MergeA(i,i + len - 1,i + 2 * len - 1);
}
if (i + len < n) {
MergeA(i,i + len - 1,n - 1);
}
}
function MergeA(low, m, hig) {
var i = low, j = m + 1, z = 0;
while (i <= m && j <= hig) {
B[z++] = (A[i] <= A[j]) ? A[i++] : A[j++];
}
while (i <= m) {
B[z++] = A[i++];
}
while (j <= hig) {
B[z++] = A[j++];
}
for (z = 0, i = low; i <= hig; z++, i++) {
A[i] = B[z];
}
}
篇7：数据结构实验报告
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1) 利用栈，实现数制转换。
2) 利用栈，实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(SqStack &S)
{
free(S.base);
return OK;
}
Status ClearStack(SqStack &S)
{
S.top=S.base;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.base==S.top)
return OK;
return ERROR;
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
Status GetTop(SqStack S,ElemType &e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Push(SqStack &S,ElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackTraverse(SqStack S)
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=S.top;
while(p!=S.base)//S.top上面一个...
{
p--;
printf(“%d ”,*p);
}
return OK;
}
Status Compare(SqStack &S)
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
printf(“请输入要进栈或出栈的元素：”);
while((x= getchar)!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf(“括号匹配成功!\\n\\n”);
break;
case ')':
if(Pop(S,e)==ERROR || e!='(')
{
printf(“没有满足条件\\n”);
flag=FALSE;
}
break;
case ']':
if ( Pop(S,e)==ERROR || e!='[')
flag=FALSE;
break;
case '}':
if ( Pop(S,e)==ERROR || e!='{')
flag=FALSE;
break;
}
}
if (flag && x=='#' && StackEmpty(S))
return OK;
else
return ERROR;
}
链队列：
Status InitQueue(LinkQueue &Q)
{
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
if(Q.front->next==NULL)
return OK;
return ERROR;
}
Status QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
if(!p)
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
while(Q.front->next )
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof (QNode));
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next = p;
Q.rear=p; //p->next 为空
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front; //只有一个元素时(不存在指向尾指针)
free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
if( QueueEmpty(Q)==OK)
{
printf(“这是一个空队列!\\n”);
return ERROR;
}
p=Q.front->next;
while(p)
{
q=p;
printf(“%d<-\\n”,q->data);
q=p->next;
p=q;
}
return OK;
}
循环队列：
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
exit(OWERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
int QueueLength(SqQueue Q)
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空
{
if(Q.front ==Q.rear)
return OK;
return ERROR;
}
Status QueueTraverse(SqQueue Q)
{
if(Q.front==Q.rear)
printf(“这是一个空队列!”);
while(Q.front%MAXQSIZE!=Q.rear)
{
printf(“%d<- ”,Q.base[Q.front]);
Q.front++;
}
return OK;
}
- 一个简单的排序问题2023-03-28
- python学习数据结构实例代码2023-01-07
- Android中对日期进行排序2022-12-27
- 语文句子排序题的技巧2024-04-28
- 海岸线数据共享分类编码与数据结构2023-01-04
- 大班数学课教案《有规律的排序》2024-02-18
- 小班数学教案设计《按高矮排序》2022-12-11
- WORD中将姓名按姓氏笔划排序2023-01-29
- 数据结构基础 单链表的设计与实现之高级操作2023-04-11
- 幼儿园中班幼儿数学教案《有趣的排序》含反思2023-04-26