`
200830740306
  • 浏览: 109466 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

排序效率分析2

    博客分类：
  • java
J#算法 
阅读更多 
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 *折半插入排序
 * @author NC
 * @version 1.0
 */
public class BInsertSorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int i, j, low, high, m;
        for (i = 2; i <= n; i++) {
            array.setKey(i); //保存关键字
            low = 1;//设定比较区间
            high = i - 1;
            while (low <= high) {
                m = (low + high) / 2;
                if (array.compareToKey(m, !order)) {
                    high = m - 1;//插入点在低半区
                } else {
                    low = m + 1;//插入点在后半区
                }
            }
            //找到插入点，开始移动，插入
            for (j = i - 1; j >= high + 1; j--) {
                array.setElement(j + 1, array.getElement(j));
                array.addMoveCount();
            }
            array.addInsertCount();
            array.setElement(high + 1, array.getKey()); //插入正确的位置
        }
    }
}

 

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 冒泡排序
 * 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
 * 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4
 * @author NC
 * @version 1.0
 */
public class BubbleSorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int i, j, flag = 1;
        for (i = n; i > 1 && flag == 1; i--) {//该趟最后一个数为关键字，假定为最大的;要求当一趟冒泡过程中不再有数据交换，则排序结束
            flag = 0;
            for (j = 1; j <= i - 1; j++) {
                if (array.compare(j, j + 1, !order)) { //关键字前面的数相邻(注意是相邻)两两比较，大的就往后冒
                    array.swap(j, j + 1);
                    flag = 1;
                }
            }
        }
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 *桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。
 * 因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在 一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。
 * @author NC
 */
public class BucketSorter extends Sorter {

    //这个方法只设正序的
    @Override
    public void sort(SortArray array, boolean order) {
                sort(array.getArray(),0,array.length,array.length*2);
                //SortArray的随机数据是1到两倍数组长度之间
    }

    public void sort(int[] array, int from, int len, int max) {
        int[] temp = new int[len];
        int[] count = new int[max];
        //分配到各个桶里面
        for (int i = 0; i < len; i++) {
            count[array[from + i]]++;
        }
        //对每个桶排序
        for (int i = 1; i < max; i++) {
            count[i] = count[i] + count[i - 1];
        }
        //按顺序把每个桶中的元素列出来
        System.arraycopy(array, from, temp, 0, len);
        for (int k = len - 1; k >= 0; k--) {
            array[--count[temp[k]]] = temp[k];
        }
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 计数排序
 * @author NC
 * @version 
 */
public class CountSorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int[] ds = new int[n]; //分配临时空间
        int i, j, count = 0;
        for (j = 1; j <= n; j++) {
            count = 0;
            for (i = 1; i <= n; i++) {
                if (i != j)//关键字与其他数比较
                {
                    if (array.compare(i, j, order)) {
                        count++;
                    } else if (array.equal(i, j) && j < i) {
                        //j<i保证排序的稳定性，去掉时当数据有一样大时会出错
                        count++;
                    }
                }
            }
            ds[count] = array.getElement(j);
        }
        array.setArray(ds);
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 堆排序
 * @author NC
 * @version 1.0
 */
public class HeapSorter extends Sorter {

    private static int heapAdjust(SortArray array, int start, int end, boolean order) {
        int flag = 0;
        int left = 0;
        int right = 0;
        int max = 0;
        left = start * 2;
        right = start * 2 + 1;
        while (left <= end) {
            max = left;
            if (right <= end) {
                if (array.compare(left, right, order)) {
                    max = right;
                } else {
                    max = left;
                }
            }
            if (array.compare(start, max, order)) {
                array.swap(start, max);
                flag = 1;
                start = max;
            } else {
                break;
            }
            left = start * 2;
            right = start * 2 + 1;
        }
        return flag;
    }

    private static void buildHeap(SortArray array, boolean order) {
        int n = array.length;
        int i;
        for (i = n / 2; i > 0; i--) {
            heapAdjust(array, i, n, order);
        }
    }

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int i;
        buildHeap(array, order);
        for (i = n; i > 1; i--) {
            array.swap(1, i);
            heapAdjust(array, 1, i - 1, order);
        }
    }
}

 

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 插入排序
 * 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。
 * 性能：比较次数O(n^2),n^2/4
 * 复制次数O(n),n^2/4
 * 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
 * @author NC
 * @version 1.0
 */
public class InsertSorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int i, j;
        for (i = 2; i <= n; i++) {
            if (array.compare(i, i - 1, order)) {//比关键字大的话
                array.setKey(i); //暂存关键字
                array.setElement(i, array.getElement(i - 1)); //比关键字大，后移（前面已经比较过了)
                array.addMoveCount();
                for (j = i - 1; j >= 1 && array.compareToKey(j, !order); j--) {//比关键字大，后移;比关键字小的话，就退出，找到要插入的位置了
                    array.setElement(j + 1, array.getElement(j));
                    array.addMoveCount();
                }
                array.setElement(j + 1, array.getKey()); //插入正确的位置
                array.addInsertCount();
            }
        }

    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 归并排序
 * @author NC
 * @version 1.0
 */
public class MergeSorter extends Sorter {

    //非递归归并排序
    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int beforeLen = 1; //合并前序列的长度
        int afterLen = 1;//合并后序列的长度
        for (beforeLen = 1; afterLen <= n; beforeLen = afterLen) {
            afterLen = beforeLen << 1; //合并后序列的长度是合并前的两倍
            int i = 1;//开始合并时第一个序列的起始位置下标，每次都是从1开始
            while (i + afterLen - 1 <= n) {//足够分成两个子表
                Merge(array, i, i + beforeLen - 1, i + afterLen - 1, order);
                i += afterLen;
            }
            if (i + beforeLen <= n) {
                Merge(array, i, i + beforeLen - 1, n, order);
            }
        }
    }

    //递归归并排序
    public void mergeSort2(SortArray array, boolean order) {
        mergeSort(array, 1, array.length, order);
    }

    //递归归并排序
    public void mergeSort2(SortArray array) {
        mergeSort(array, 1, array.length, Sorter.POSITIVE);
    }

    private void mergeSort(SortArray array, int left, int right, boolean order) {

        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(array, left, center, order);
            mergeSort(array, center + 1, right, order);
            Merge(array, left, center, right, order);
        }
    }

    private void Merge(SortArray array, int left, int center, int right, boolean order) {
        //[1,2,3,4] left=1,ceter=2,right=4
        int[] temp = new int[right - left + 1];//存放被合并后的元素
        int i = left;
        int j = center + 1;
        int k = 0;
        while (i <= center && j <= right) {
            array.addInsertCount();
            if (array.compare(i, j, order)) {
                temp[k++] = array.getElement(i++);
            } else {
                temp[k++] = array.getElement(j++);
            }
        }
        while (i <= center) {
            array.addInsertCount();
            temp[k++] = array.getElement(i++);
        }
        while (j <= right) {
            array.addInsertCount();
            temp[k++] = array.getElement(j++);
        }
        //把t[]的元素复制回a[]
        for (i = left, k = 0; i <= right; i++, k++) {
            array.setElement(i, temp[k]);
        }
    }
}

 

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 奇偶交换排序
 * @author NC
 * @version
 */
public class ParitySorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int i = 0, j = 0, tag = 1;
        for (j = 0; j < n; j++) {
            for (i = j % 2 + 1; i <= n - 1; i += 2) {
                //每次仅对奇数或偶数下标处理，步长为2
                if (array.compare(i, i + 1, !order)) {
                    array.swap(i, i + 1);
                    tag = 0;//记录比较趟数
                }
            }
            tag++;
            if (tag == 3) {
                break;
            }
            /*如果待排序列本身已经有序，
            则只需执行再次内层循环即对奇偶下标元素分别扫描一次
            就可判断出序列已经有序*/
        }
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 快速排序
 * 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
 * 步骤为：
 * 1. 从数列中挑出一个元素，称为 "基准"（pivot），
 * 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 *    在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
 * 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 * 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。
 *    虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
 * @author NC
 * @version 1.0
 */
public class QuickSorter extends Sorter {

    private int partition(SortArray array, int low, int high, boolean order) {
        int key = array.getElement(low); //用子表的第一个记录作为枢轴记录
        while (low < high) {//从表的两端交替地向中间扫描
            while (low < high && array.compareNotMoreThan(array.getElement(high), key, !order)) {
                high--;
            }
            array.setElement(low, array.getElement(high));
            while (low < high && array.compareNotMoreThan(array.getElement(low), key, order)) {
                low++;
            }
            array.setElement(high, array.getElement(low));
            array.addExchangeCount();
        }
        array.setElement(low, key);
        array.addInsertCount();
        return low;
    }

    private void qSort(SortArray array, int low, int high, boolean order) {
        int pivotloc;
        if (low < high) {//保证长度大于1，递归的出口
            pivotloc = partition(array, low, high, order); //将表low-high一分为2，用枢轴位置来分
            qSort(array, low, pivotloc - 1, order); //对低子表递归排序
            qSort(array, pivotloc + 1, high, order); //对高子表递归排序
        }
    }

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        qSort(array, 1, n, order);
    }
}

 

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 选择排序
 * 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
 * 性能：比较次数O(n^2),n^2/2
 * 交换次数O(n),n
 * 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
 * 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
 * @author NC
 * @version 1.0
 */
public class SelectSorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int x, k, i, j;
        for (i = 1; i < n; i++) {
            k = i; //暂时定为最小的关键字
            for (j = i + 1; j <= n; ++j) {
                if (array.compare(j, k, order)) {
                    k = j; //与i之后的n-i个数依次比较，记录小值下标
                }
            }
            if (k != i) {//k值改变，原先定的不是最小。找到最小的，交换
                array.swap(i, k);
            }
        }
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package nc.norman.sorter;

/**
 * 希尔排序
 * @author NC
 * @author 1.0
 */
public class ShellInsertSorter extends Sorter {

    @Override
    public void sort(SortArray array, boolean order) {
        int n = array.length;
        int k = n / 2;
        while (k > 0) {
            shellInsert(array, k, order);
            k = k / 2; //分配增量
        }
    }

    private void shellInsert(SortArray array, int dk, boolean order) {
        int n = array.length;
//dk为增量
        int i, j;
        for (i = dk + 1; i <= n; i++) {
//共n-(dk+1)+1个子序列，分别进行直接插入排序
            if (array.compare(i, i - dk, order)) {//比关键字大的话
                array.setKey(i); //暂存关键字
                for (j = i - dk; j > 0 && array.compareToKey(j, !order); j = j - dk) {//比关键字小的就退出，找到位置了。j<=0说明方序列已经是有序的
                    array.setElement(j + dk, array.getElement(j)); //记录后移，找到插入位置时退出
                    array.addMoveCount();
                }
                array.setElement(j + dk, array.getKey()); //插入关键字
                    array.addInsertCount();
            }
        }
    }
}

源码请见上一篇的附件 

分享到：
| 排序效率分析1(源码+报告)
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    排序算法效率分析-动态显示排序过程

    《排序算法效率分析——动态显示排序过程》 在信息技术领域，排序算法是计算机科学的基础，其性能直接影响到程序的运行效率。本软件是由资深算法研究者精心编写的，旨在通过动态展示排序算法的过程，帮助用户深入...

    多种排序算法效率分析

    通过几组有代表意义的随机数据的比较，算出几种这几种排序算法的关键字比较次数和关键字移动次数，以便我们分析算法效率。 1、通过修改程序，实现程序在要求的数据量下求出以下六种内部排序算法的移动次数和比较次数...

    c语言实现的各种排序算法效率分析与比较及源代码

    各种排序算法效率分析比较及源代码 C语言实现 各种排序包括： 直接插入排序，折半插入排序，2—路插入排序和表插入排序；希尔排序和链式基数排序；起泡排序，快速排序，归并排序；简单选择排序，树形选择排序和堆...

    各种排序的实现与效率分析

    本文章将对各种排序算法的原理、实现及其效率进行深入分析。 1. 直接插入排序 直接插入排序的基本原理是把数据集视为一个有序表和一个待插入的元素，将待插入元素插入到有序表中的适当位置，保持有序表的有序状态。...

    算法设计与分析-排序算法性能分析-要求pdf 报告文档 c++源代码 preppt

    不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示排序结果 void Select_Sort();//选择排序函数声明 void Bubble_...

    排序算法效率比较(含报告)

    2. 数据特性：数据是否已经部分有序、是否存在重复元素等都会影响排序效率。 3. 时间复杂度：理论上的时间复杂度是衡量算法效率的重要指标，但实际运行时间还取决于具体实现和硬件环境。 4. 空间复杂度：除了运行...

    内部排序算法分析

    在《数据结构课程设计》中，你可能需要设计并实现这些排序算法，理解它们的原理，以及如何在C语言环境下优化代码，以提高排序效率。同时，通过对各种算法的比较和测试，可以更好地理解它们在不同场景下的适用性。

    C++排序算法效率分析

    本文将深入探讨C++中几种常见的排序算法及其效率分析。C++作为一门强类型、静态类型的编程语言，提供了丰富的库函数和机制来实现高效排序。 首先，我们来了解基本的排序算法类型。冒泡排序是最基础的排序算法，它...

    算法设计与分析-1排序算法性能分析-冒泡/选择/插入/合并/快速排序-pre ppt

    本篇文章将详细讨论几种常见的排序算法：选择排序、冒泡排序、插入排序、合并排序以及快速排序，分析它们的算法原理、时间效率，并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...

    c++实现比较各种排序算法的效率

    冒泡排序的时间复杂度为O(n^2)，在处理大量数据时效率较低。 **插入排序** 的工作原理类似于手动整理扑克牌，每次将一个待排序的元素插入到已排序的序列中的适当位置。它在最好情况（已排序）下的时间复杂度为O(n)...

    各种排序方法分析详解

    【各种排序方法分析详解】 排序算法是计算机科学中不可或缺的一部分，尤其在处理大量数据时，高效排序算法能够显著提升程序的运行效率。本文将详细介绍五种经典的排序算法：插入排序、希尔排序、冒泡排序、选择排序...

    数据结构各种排序方法的效率分析与比较

    数据结构各种排序方法的效率分析与比较 包括随机数列，正序数列，反序数列的比较分析

    比较常用的排序效率（C/C++数据结构）

    本文将深入探讨在C/C++编程语言中，用于处理大数据集（如80000多个整数）的几种常见排序算法，并分析它们的效率。我们将主要关注快速排序、归并排序、堆排序、冒泡排序和插入排序这五种经典算法。 1. **快速排序**...

    如何解决Oracle分页查询中排序与效率问题

    本文主要解决 Oracle 分页查询中排序与效率问题，通过实践和分析，提供了两种解决方案，并对比了两种方法的优缺点。 知识点 1: Oracle 分页查询的基本概念 Oracle 分页查询是指在查询结果中，通过限制行数来实现...

    排序算法分析内含程序和论文

    此外，如果论文涉及到了优化，可能还包括了对现有算法的改进，比如引入并行化、使用启发式策略或优化数据结构来提升排序效率。这种分析对于理解和设计更高效的算法非常有价值。 总之，这个压缩包中的内容对于学习和...

    排序及性能分析

    在IT领域，排序算法是计算机科学中的基础但至关重要的部分，尤其在系统设计和数据分析中。本文将深入探讨五种常见的排序算法：插入排序、归并排序、堆排序、快速排序以及冒泡排序，并在Linux环境下用C语言实现它们，...

    算法设计与分析-排序算法源代码

    不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示排序结果 void Select_Sort();//选择排序函数声明 void Bubble_...

    利用C51验证快速排序效率

    利用C51，定时器T2，分析快速排序与其它方式排序效率差异

Magicbox
Global site tag (gtag.js) - Google Analytics