`

java排序算法

阅读更多
java排序算法

1.排序

排序是一个历来都是很多算法家热衷的领域,到现在还有很多数学家兼计算机专家还在研究。而排序是计算机程序开发中常用的一种操作。为何需要排序呢。我们在所有的系统中几乎都要检索数据,而这些欲检索的数据如果有规律的话,比如按照某些字段、属性降序排序的话,那么从这些有规律的数据查询结果或者结果集的话就快速得多。

2. 常用算法

常用的算法有:直接选择排序、堆排序、冒泡排序、快速交换排序、直接插入排序、折半插入排序、Shell排序、归并排序、桶式排序、基数排序。这些都属于常用排序算法,也都是内部排序算法。所谓内部排序就是不借助任何外部的内存处理器,直接使用内存,在内存中完成就可以的排序方式。

3.直接选择排序

直接排序的思想就是进行二重遍历,由外层元素依次和内层元素进行对比,之后交换位置。算法如下
    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 选择排序
     */ 
    public class SelectSort { 
     
        // 选择排序法 
        public static void selectSort(Integer[] integers) { 
            for (int i = 0; i < integers.length - 1; i++) { 
                int minIndex = i; 
                for (int j = i + 1; j < integers.length; j++) { 
                    if (integers[i] < integers[j] 
                            && integers[minIndex] < integers[j]) { 
     
                        // 只记住标记 
                        minIndex = j; 
                    } 
                } 
     
                // 每次只交换一次即可 
                if (minIndex != i) { 
                    Integer temp = integers[i]; 
                    integers[i] = integers[minIndex]; 
                    integers[minIndex] = temp; 
                } 
            } 
        } 
    } 


4.堆排序

堆排序的思想就是将要排序的数组看成一个完全二叉树(出最后一层节点外,其他节点都是2个子节点),之后建立大顶堆,将完全二叉树建立成一个父节点值都大于它的子节点的树。之后将根节点和要排序的数组的最后一个元素进行换位。之后除了数组最后一个元素外重复建堆过程。算法如下

    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 堆排序
     */ 
    public class HeapSort { 
     
        /**
         * 构建堆数组
         * @param datas
         * @param lastIndex
         */ 
        public static void buildHeap(Integer[] datas, int lastIndex) { 
             
            //从目标的父节点开始遍历 
            for (int i = (lastIndex - 1) / 2; i >= 0; i--) { 
                 
                //记录父节点位置 
                int maxIndex = i; 
                 
                //当父节点的子节点存在的时候 
                while (maxIndex * 2 + 1 <= lastIndex) { 
                     
                    //默认附一个大值为父节点的左子节点的索引 
                    int biggerIndex = maxIndex * 2 + 1; 
                     
                    //此处判断是否父节点还有一个右子节点 
                    if (biggerIndex < lastIndex) { 
                         
                        //如果有右子节点判断左右子节点的值大小,记录一个最大的位置,好用于交换 
                        if (datas[biggerIndex] < datas[biggerIndex + 1]) { 
                            biggerIndex++; 
                        } 
     
                    } 
                     
                    //此处是比较父节点值和左右子节点值,找个最大的做父亲 
                    if (datas[maxIndex] < datas[biggerIndex]) { 
                        Integer temp = datas[maxIndex]; 
                        datas[maxIndex] = datas[biggerIndex]; 
                        datas[biggerIndex] = temp; 
                         
                        //记录一下最大值的索引 
                        maxIndex = biggerIndex; 
                    } else { 
                        break; 
                    } 
     
                } 
     
            } 
     
        } 

        /**
         * 堆排序
         * @param datas
         */ 
        public static void heapSort(Integer[] datas) { 
     
            // 数组大小 
            int arrayLength = datas.length; 
     
            // 遍历数组 
            for (int i = 0; i < arrayLength - 1; i++) { 
     
                // 构建堆 
                buildHeap(datas, arrayLength - 1 - i); 
     
                // 交换元素 
                Integer temp = datas[0]; 
                datas[0] = datas[arrayLength - 1 - i]; 
                datas[arrayLength - 1 - i] = temp; 
            } 
        }
    }




5.冒泡排序

冒泡排序在使用频率上来说,也许是仅次于直接选择排序的算法的了。因为起泡的思想也很简单就是循环数组中的元素,相邻元素一一对比,进行交换。算法如下


    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 冒泡排序法
     */ 
    public class BubbleSort { 
     
        /**
         * 冒泡排序
         * @param datas
         */ 
        public static void bubbleSort(Integer[] datas) { 
            int datasLength = datas.length; 
            for (int i = 0; i < datasLength - 1; i++) { 
                for (int j = 0; j < datasLength - 1 - i; j++) { 
                    if (datas[j] < datas[j + 1]) { 
     
                        // 交换之 
                        Integer temp = datas[j + 1]; 
                        datas[j + 1] = datas[j]; 
                        datas[j] = temp; 
                    } 
                } 
            } 
     
        } 
     
    } 


6. 快速排序

所谓快速排序法是从待排序的数组中找一个标本作为分界值(一般是数组的第一个元素),所有比这个值小的值放到它的左边(或者右边),将比它大的值放到它的右边(或者左边),这样这个分界值左右两边的值要么全部比它大,要么全部比它小。之后再利用递归,将此标本右边、左边的所有元素也按部就班。算法如下 

    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 快速排序
     */ 
    public class QuickSort { 
     
        /**
         * 交换数组元素位置
         * @param datas
         * @param i
         * @param j
         */ 
        public static void chang(Integer[] datas, int i, int j) { 
            Integer temp = datas[i]; 
            datas[i] = datas[j]; 
            datas[j] = temp; 
     
        } 
     
        /**
         * 快速排序法
         * @param datas
         * @param startIndex
         * @param endIndex
         */ 
        public static void quickSort(Integer[] datas, int startIndex, int endIndex) { 
     
            if (startIndex < endIndex) { 
                 
                //标本 
                Integer startData = datas[startIndex]; 
                 
                //左边的开始索引 
                int i = startIndex; 
                 
                //右边的开始索引 
                int j = endIndex + 1; 
                while (true) { 
                     
                    //找左边比标本大的下标 
                    while (i < endIndex && datas[++i] > startData){ 
                    } 
                     
                    //找右边比标本小的下标 
                    while (j > startIndex && datas[--j] < startData){ 
                    } 
                         
                    if (i < j) { 
                         
                        //交换i、j元素位置 
                        chang(datas, i, j); 
                    } else { 
                        break; 
                    } 
                } 
                 
                //交换开始位置、j的元素为止 
                chang(datas, startIndex, j); 
                 
                //递归标本左边 
                quickSort(datas, startIndex, j - 1); 
                 
                //递归标本右边 
                quickSort(datas, j + 1, endIndex); 
            } 
     
        } 
    } 


7.直接插入排序

直接插入排序的原理就是将数组中的元素依次和前面元素进行比较,如果发现了比它大的(或者小的),记录标志位、记录被比较元素,之后从标志位一位一位的向后进行元素移动,之后空出来的的那一位就是留给被比较元素的。这样造成了一个现象就是被比较的元素前面的所有元素都是排序过了的。算法如下。


    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 直接插入排序
     */ 
    public class InsertSort { 
     
        /**
         * 直接插入
         * @param datas
         */ 
        public static void insertSort(Integer[] datas) { 
             
            //从数组第二个元素开始遍历 
            for (int i = 1; i < datas.length; i++) { 
                 
                //当前元素和前一个元素进行对比【此处前面的元素已经排序好了】 
                if (datas[i] < datas[i - 1]) { 
                     
                    //记录当前要比较的元素值 
                    Integer temp = datas[i]; 
                     
                    //从当前元素往前开始比较 
                    int j = i - 1; 
                     
                    //如果满足前面索引有效并且前面的元素值都是比当前值大的,那就进行元素后移动操作 
                    for (; j >= 0 && datas[j] > temp; j--) { 
                         
                        //元素后移 
                        datas[j + 1] = datas[j]; 
     
                    } 
                     
                    //前移操作后,j的索引就是中间那个比前面元素大,比后面元素小的位置索引-1 
                     
                    //将其要对比的值插进去 
                    datas[j + 1] = temp; 
                } 
     
            } 
        } 
    } 


8.折半插入排序

折半插入排序是在原直接插入的基础上作了改进。对于折半插入法,被比较的元素不用和前面所有的元素进行一一对比,而是先找到0位元素到此被比较元素的中点元素,和这个重点元素进行比较,看看谁大,之后就是被比较元素元素和这个中点元素之间再找一个中点进行比较,或者是0点和原中点元素找个新中点。这样就可以缩小范围,反正排在被比较元素之前的元素是一个已经排好大小的序列,那就可以善加利用这已经排好的序列。当然了,找到位置后,该移动元素的还是要移动的。算法如下:

    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 折半排序
     */ 
    public class BinaryInsertSort { 
     
        /**
         * 折半排序
         * @param datas
         */ 
        public static void binaryInsertSort(Integer[] datas) { 
     
            // 从数组第二个元素开始遍历 
            for (int i = 1; i < datas.length; i++) { 
     
                // 记录当前要比较的元素值 
                Integer temp = datas[i]; 
     
                // 低位开始 
                int low = 0; 
     
                // 高位开始 
                int hight = i - 1; 
     
                // 位置有效,低位、高位 
                while (low <= hight) { 
     
                    // 中间位置 
                    int mind = (low + hight) / 2; 
                     
                    //被比较元素大于中间元素 
                    if (temp > datas[mind]) { 
                         
                        //低位调整在中点之后 
                        low = mind + 1; 
                    } else {//被比较元素小于中间元素 
                         
                        //高位在中点之前 
                        hight = mind - 1; 
                    } 
                } 
                // 低高位调整完毕后,将中点元素依次往后移动 
                for (int j = i; j > low; j--) { 
     
                    // 元素后移 
                    datas[j] = datas[j - 1]; 
     
                } 
     
                // 前移操作后,low的索引就是中间那个比前面元素大,比后面元素小的位置索引low 
                // 将其要对比的值插进去 
                datas[low] = temp; 
            } 
        } 
    } 


9.归并排序

归并排序的主要思想就是将原来的数组分开成2大部分,建立一个新的临时数组,分别从2部分开始顺序走,将2部分的元素进行比较,先将小元素放入到临时数组,之后索引往前走一位,剩下的在进行比较。算法如下:


    package sort; 
     
    import java.util.Arrays; 
     
    /**
     * 归并排序
     * @author liuyan
     */ 
    public class MergeSort { 
     
        /**
         * 归并排序
         * @param datas
         * @param start
         * @param datasLength
         */ 
        public static void mergeSort(Integer[] datas, int leftIndex, int rightIndex) { 
             
            //当分块索引有效时 
            if (leftIndex < rightIndex) { 
                 
                //找出中间索引 
                int center = (leftIndex + rightIndex) / 2; 
                 
                //把左边到中点的元素集合继续分堆儿 
                mergeSort(datas, leftIndex, center); 
                 
                //把右边到中点的元素集合继续分堆儿 
                mergeSort(datas, center + 1, rightIndex); 
                 
                //归并 
                merge(datas, leftIndex, center, rightIndex); 
            } 
     
        } 
     
        /**
         * 归并
         * @param datas
         * @param left
         * @param center
         * @param right
         */ 
        private static void merge(Integer[] datas, int left, int center, int right) { 
             
            //建立一个临时的数组,用于装载排序后的数组 
            Integer[] temp = new Integer[datas.length]; 
             
            //第二队的开始索引位置 
            int mind = center + 1; 
             
            //临时数组从第一队的索引开始 
            int third = left; 
             
            //仅仅记录开始索引位置 
            int tmp = left; 
            while (left <= center && mind <= right) {//分队后的数组进行比较 
                if (datas[left] <= datas[mind]) { 
                     
                    //左边的略小,左边索引前进 
                    temp[third++] = datas[left++]; 
                } else { 
                     
                    //右边的略小,右边索引前进 
                    temp[third++] = datas[mind++]; 
                } 
     
            } 
             
            //如果第二队数组还没走完,继续走完,将第二队右边的元素都放到临时数组后面 
            while (mind <= right) { 
                temp[third++] = datas[mind++]; 
            } 
             
            //如果第一队数组还没走完,继续走完,将第一队右边的元素都放到临时数组后面 
            while (left <= center) { 
                temp[third++] = datas[left++]; 
            } 
             
            //将临时数组中的所有元素(排序好的),原样覆盖到原先的数组 
            while (tmp <= right) { 
                datas[tmp] = temp[tmp++]; 
            } 
        } 
    } 


此文为转载,忘了原文地址

分享到:
评论

相关推荐

    java排序算法使用及场景说明

    Java 排序算法使用及场景说明 本文档主要介绍了 Java 排序算法的使用和场景说明,包括了五个实践场景的解决方案。 Scenario 1: 找出两个文件共同的 URL 在这个场景中,我们有两个文件 a 和 b,每个文件中存放了 ...

    Java排序算法大全

    Java排序算法大全是一份专为Java开发者准备的学习资源,涵盖了各种经典的排序算法,旨在帮助初学者和有经验的程序员深入理解排序的原理和实现。排序是计算机科学中的基础且重要的概念,它在数据处理、数据库操作、...

    Java排序算法实现

    Java排序算法实现 Java排序算法实现 Java排序算法实现

    java排序算法插入选择冒泡

    java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡

    java排序算法效率比较

    在Java编程语言中,排序算法是数据结构与算法学习中的重要组成部分。本实验通过生成大量随机数并写入文件,然后使用四种不同的排序算法进行排序,以比较它们的效率。以下是对这四种排序算法的详细解释: 1. **冒泡...

    Java排序算法详细整理

    【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...

    Java排序算法包 支持自定义比较条件

    这个"Java排序算法包"提供了对多种排序算法的支持,并且允许用户根据自己的需求自定义比较条件,使得排序功能更加灵活。 1. **排序算法基础**: - 排序是指将一组数据按照特定的顺序进行排列的过程。常见的排序...

    Java排序算法 Java排序算法.rar

    Java排序算法涉及了多种方法,用于组织数组或集合中的元素,使其按照特定顺序排列。以下是对这些算法的详细解释: 1. **冒泡排序(Bubble Sort)** 冒泡排序是一种简单直观的排序算法,它重复地遍历待排序的数列,一...

    java 排序算法

    代码中列举了java常见的排序算法,并备有简单的注释信息,对于初级开发人员可供参考。

    Java排序算法详解.rar

    Java排序算法涉及了多种方法,每种都有其特定的适用场景和性能特点。本篇将深入探讨几种常见的Java排序算法,包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序以及TimSort等。 1. **冒泡排序**: ...

    java排序算法-大全.rar

    这个名为"java排序算法-大全.rar"的压缩包文件显然包含了多种Java实现的排序算法,这对于我们理解和掌握这些算法至关重要。 首先,让我们从标签提及的两个经典排序算法开始:冒泡排序和折半排序。 1. **冒泡排序**...

    java排序算法演示源码

    本资源提供了丰富的Java排序算法的演示源码,注解详尽,有助于理解和学习。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一,通过不断地交换相邻的不正确顺序的元素来逐步完成排序。源码中应该...

    面试笔试必用-必须掌握的Java排序算法

    Java排序算法是编程面试和笔试中常见的考察点,掌握这些算法对于提升编程能力和解决实际问题至关重要。本篇文章将深入探讨几种主要的Java排序算法及其特点。 1. **插入排序** - **直接插入排序**:将每个元素依次...

    Java排序算法汇总大全.doc

    Java排序算法汇总大全 在计算机科学中,排序算法是用于对数据序列进行排列的算法,以便根据特定标准对其进行组织。本文将详细介绍Java中常见的几种排序算法,并提供它们的基本原理、性能分析以及适用场景。 1. ...

    各种排序算法比较(java实现)

    本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**: 合并排序是一种基于分治策略的排序算法...

    Java排序算法_java_

    Java排序算法是编程领域中的重要知识点,特别是在处理大量数据时,高效的排序算法能显著提升程序性能。本资源包含了Java实现的常见排序算法集合,对于学习和理解这些算法有着极大的帮助。 1. 冒泡排序(Bubble Sort...

    java排序算法集合

    【Java排序算法集合】 在Java编程中,排序算法是数据结构和算法中不可或缺的一部分,它用于将一组数据按照特定的顺序排列。常见的排序算法包括选择排序、冒泡排序和插入排序,下面我们将逐一探讨这些算法的基本思想...

Global site tag (gtag.js) - Google Analytics