本文作者:大发快3辅助_快3网页版_是真实吗|

海城鸿尊永乐汇温泉电话,高效的排序算法

摘要: 1 概述本文对比较常用且比较海城鸿尊永乐汇温泉电话,高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示:&...

1 概述

本文对比较常用且比较海城鸿尊永乐汇温泉电话,高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示:


海城鸿尊永乐汇温泉电话,高效的排序算法  第1张

 

2 选择排序

选择排序的第一趟处理是从数据序列所有n个数据中选择一个最小的数据作为有序序列中的第1个元素并将它定位在第一号存储位置,第二趟处理从数据序列的n-1个数据中选择一个第二小的元素作为有序序列中的第2个元素并将它定位在第二号存储位置,依此类推,当第n-1趟处理从数据序列的剩下的2个元素中选择一个较小的元素作为有序序列中的最后第2个元素并将它定位在倒数第二号存储位置,至此,整个的排序处理过程就已完成。

    代码如下:

海城鸿尊永乐汇温泉电话,高效的排序算法  第2张
public class SelectionSort {    public void selectionSort(int[] array) {        int temp;        for (int i = 0; i < array.length - 1; i++) {            for (int j = i + 1; j <= array.length - 1; j++) {// 第i个和第j个比较j可以取到最后一位,所以要用j<=array.length-1
                if (array[i] > array[j]) {// 注意和冒泡排序的区别,这里是i和j比较。
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }            // 打印每趟排序结果
            for (int m = 0; m <= array.length - 1; m++) {
                System.out.print(array[m] + "\t");
            }
            System.out.println();
        }
    }  
    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        selectionSort.selectionSort(array);        for (int m = 0; m <= array.length - 1; m++) {
            System.out.print(array[m] + "\t");
        }
    }
}
海城鸿尊永乐汇温泉电话,高效的排序算法  第2张

 

3 插入排序

     直接插入排序法的排序原则是:将一组无序的数字排列成一排,左端第一个数字为已经完成排序的数字,其他数字为未排序的数字。海城鸿尊永乐汇温泉电话然后从左到右依次将未排序的数字插入到已排序的数字中。

    代码如下:

海城鸿尊永乐汇温泉电话,高效的排序算法  第2张
public class InsertSort {    public void insertSort(int[] array, int first, int last) {        int temp, i, j;        for (i = first + 1; i <= last - 1; i++) {// 默认以第一个数为有序序列,后面的数为要插入的数。
            temp = array[i];
            j = i - 1;            while (j >= first && array[j] > temp) {// 从后进行搜索如果搜索到的数小于temp则该数后移继续搜索,直到搜索到小于或等于temp的数即可
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;            // 打印每次排序结果
            for (int m = 0; m <= array.length - 1; m++) {
                System.out.print(array[m] + "\t");
            }
            System.out.println();
        }
    }  
    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        insertSort.insertSort(array, 0, array.length);// 注意此处是0-9而不是0-8
        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}
海城鸿尊永乐汇温泉电话,高效的排序算法  第2张

4 归并排序

    算法描述:

        把序列分成元素尽可能相等的两半。

海城鸿尊永乐汇温泉电话        把两半元素分别进行排序。

        把两个有序表合并成一个。

    代码如下:

海城鸿尊永乐汇温泉电话,高效的排序算法  第2张
public class MergeSortTest {    public void sort(int[] array, int left, int right) {        if (left >= right)            return;        // 找出中间索引
        int center = (left + right) / 2;        // 对左边数组进行递归        sort(array, left, center);        // 对右边数组进行递归
        sort(array, center + 1, right);        // 合并        merge(array, left, center, right);        // 打印每次排序结果
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
  
    }  
    /**
     * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
     * 
     * @param array
     *            数组对象
     * @param left
     *            左数组的第一个元素的索引
     * @param center
     *            左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
     * @param right
     *            右数组最后一个元素的索引     */
    public void merge(int[] array, int left, int center, int right) {        // 临时数组
        int[] tmpArr = new int[array.length];        // 右数组第一个元素索引
        int mid = center + 1;        // third 记录临时数组的索引
        int third = left;        // 缓存左数组第一个元素的索引
        int tmp = left;        while (left <= center && mid <= right) {            // 从两个数组中取出最小的放入临时数组
            if (array[left] <= array[mid]) {
                tmpArr[third++] = array[left++];
            } else {
                tmpArr[third++] = array[mid++];
            }
        }        // 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
        while (mid <= right) {
            tmpArr[third++] = array[mid++];
        }        while (left <= center) {
            tmpArr[third++] = array[left++];
        }        // 将临时数组中的内容拷贝回原数组中        // (原left-right范围的内容被复制回原数组)
        while (tmp <= right) {
            array[tmp] = tmpArr[tmp++];
        }
    }  
    public static void main(String[] args) {        int[] array = new int[] { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        MergeSortTest mergeSortTest = new MergeSortTest();
        mergeSortTest.sort(array, 0, array.length - 1);
        System.out.println("排序后的数组:");        for (int m = 0; m <= array.length - 1; m++) {
            System.out.print(array[m] + "\t");
        }
    }
}
海城鸿尊永乐汇温泉电话,高效的排序算法  第2张

 5 希尔排序

希尔排序又称“缩小增量排序”,该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某 个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插 入排序。海城鸿尊永乐汇温泉电话因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。


    代码如下:

海城鸿尊永乐汇温泉电话,高效的排序算法  第2张
public class ShellSort {    public void shellSort(int[] array, int n) {        int i, j, gap;        int temp;        for (gap = n / 2; gap > 0; gap /= 2) {// 计算gap大小
            for (i = gap; i < n; i++) {// 将数据进行分组
                for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {// 对每组数据进行插入排序
                    temp = array[j];
                    array[j] = array[j + gap];
                    array[j + gap] = temp;
                }                // 打印每趟排序结果
                for (int m = 0; m <= array.length - 1; m++) {
                    System.out.print(array[m] + "\t");
                }
                System.out.println();
            }
        }
    }  
    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        shellSort.shellSort(array, array.length);// 注意为数组的个数
        for (int m = 0; m <= array.length - 1; m++) {
            System.out.print(array[m] + "\t");
        }
    }
}
海城鸿尊永乐汇温泉电话,高效的排序算法  第2张

 6 快速排序

    快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然 后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    代码如下:

海城鸿尊永乐汇温泉电话,高效的排序算法  第2张
public class QuickSort {    public int partition(int[] sortArray, int low, int height) {        int key = sortArray[low];// 刚开始以第一个数为标志数据
        while (low < height) {            while (low < height && sortArray[height] >= key)
                height--;// 从后面开始找,找到比key值小的数为止
            sortArray[low] = sortArray[height];// 将该数放到key值的左边
            while (low < height && sortArray[low] <= key)
                low++;// 从前面开始找,找到比key值大的数为止
            sortArray[height] = sortArray[low];// 将该数放到key值的右边        }
        sortArray[low] = key;// 把key值填充到low位置,下次重新找key值        // 打印每次排序结果
        for (int i = 0; i <= sortArray.length - 1; i++) {
            System.out.print(sortArray[i] + "\t");
        }
        System.out.println();        return low;
    }  
    public void sort(int[] sortArray, int low, int height) {        if (low < height) {            int result = partition(sortArray, low, height);
            sort(sortArray, low, result - 1);
            sort(sortArray, result + 1, height);
        }
    }  
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        quickSort.sort(array, 0, 8);        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}
海城鸿尊永乐汇温泉电话,高效的排序算法  第2张

 

  这里只贴出了自己总结的部分排序算法,更多的算法总结可参考自己另外一篇文章:Java自学之道

 

  原创文章欢迎转载,转载时请注明出处。



推荐阅读:

浅谈为什么内部文章很重要?如何在链内建立一篇文章?

支付宝康师傅集5张康卡组成100%得1.66-666元红包 秒到账

微信聊天你打开整人怎么搞?抖音上很热的微信你点开表情包下载

文章版权及转载声明:

作者:大发快3辅助_快3网页版_是真实吗|本文地址:http://rangyuanfei.com/blog/1550.html发布于 2个月前 ( 08-09 )
文章转载或复制请以超链接形式并注明出处大发快3辅助_快3网页版_是真实吗|