常用排序算法

直接插入排序

基本思想：在要排序的一组数中，假设前面 (n - 1)[n >= 2] 个数已经是排好顺序的，现在要把第 n 个数插到前面的有序数中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。

直接插入排序

/*
     * 直接插入排序
     */
    public static void insertSort(int[] array) {
        
        for(int i = 1; i < array.length; i++ ) {
            
            int temp = array[i];
            int j = i - 1;
            for(; j >=0; j --) {
                
                if(array[j] > temp)
                    array[j + 1] = array[j];
                else
                    break;
            }
            array[j + 1] = temp;
        }
    }

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高级的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

基本思想：先取一个正整数 d₁ < n，把所有相隔 d₁ 的记录放一组，每个组内进行直接插入排序；然后 d₂ < d₁，重复上述分组和排序操作；直到 d_i = 1，即所有记录放进一个组中排序为止。

希尔排序

/*
     * 希尔排序
     */
    public static void shellSort(int[] array) {
        
        int i, j;
        int temp;
        int gap = 1;
        int len = array.length;
        while(gap < len / 3) {
            
            gap = gap * 3 + 1;
        }
        for(; gap > 0; gap /= 3) {
            
            for(i = gap; i < len; i ++) {
                
                temp = array[i];
                for(j = i - gap; j >=0; j -= gap) {
                    
                    if(array[j] > temp)
                        array[j + gap] = array[j];
                    else
                        break;
                }
                array[j + gap] = temp;
            }
        }
    }

简单选择排序

基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

简单选择排序

    /*
     * 简单选择排序
     */
    public static void selectSort(int[] array) {
        
        int position = 0;
        for(int i = 0; i < array.length; i ++) {
            
            int temp = array[i];
            int j = i + 1;
            position = i;
            for(; j < array.length; j ++) {
                
                if(array[j] < temp) {
                    
                    temp = array[j];
                    position = j;
                }
            }
            array[position] = array[i];
            array[i] = temp;
        }
    }

堆排序

基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有 n 个元素的序列（h₁,h₂,...,h_n），当且仅当满足（h_i >= h_2i,h_i >= h_2i+1）或（h_i <= h_2i,h_i <= h_2i+1）（i = 1,2,...,n / 2）时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大顶（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一颗顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面（n - 1）个数重新调整使之成为堆。以此类推，直到只有两个节点的堆，并对它们作交换，最后得到有 n 个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一个是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

建堆

交换

再建堆

/*
     * 堆排序
     */
    public static void heapSort(int[] array) {
        
        int len = array.length - 1;
        int beginIndex = (len - 1) >> 1;
        for(int i = beginIndex; i >= 0; i --) {
            
            maxHeapify(i, len, array);
        }
        for(int i = len; i > 0; i --) {
            
            swap(0, i, array);
            maxHeapify(0, i - 1, array);
        }
    }
    private static void swap(int i, int j, int[] array) {
        
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    private static void maxHeapify(int index, int len, int[] arr) {
        
        int li = (index << 1) + 1;
        int ri = li + 1;
        int cMax = li;
        if(li > len) {
            
            return;
        }
        if(ri <= len && arr[ri] > arr[li]) {
            
            cMax = ri;
        }
        if(arr[cMax] > arr[index]) {
            
            swap(cMax, index, arr);
            maxHeapify(cMax, len, arr);
        }
    }

冒泡排序

基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较它们的排序与排序要求相反时，就将它们互换。

冒泡排序

/*
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        
        int temp = 0;
        for(int i = 0; i < array.length - 1; i ++) {
            
            for(int j = 0; j < array.length - 1; j ++) {
                
                if(array[j] > array[j + 1]) {
                    
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

快速排序

基本思想：选择一个基准元素，通常选择第一个元素或者最后一个元素，通过一趟扫描，将待排序序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。

快速排序

/*
     * 快速排序
     */
    public static void quickSort(int[] array) {
        
        quickSort(array, 0, array.length - 1);
    }
    private static void quickSort(int[] array, int left, int right) {
        
        if(left >= right)
            return;
        int i = left;
        int j = right;
        int temp = array[left];
        while(i < j) {
            
            while(i < j) {
                if(array[j] >= temp)
                    j --;
                else
                    break;
            }
            array[i] = array[j];
            while(i < j) {
                
                if(array[i] <= temp)
                    i ++;
                else
                    break;
            }
            array[j] = array[i];
        }
        array[i] = temp;
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }

归并排序

基本思想：归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分成若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。

归并排序

/*
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        
        mergeSort(array, 0, array.length - 1);
    }
    private static void mergeSort(int[] array, int left, int right) {
        
        if(left < right) {
            
            int center = (left + right) / 2;
            mergeSort(array, left, center);
            mergeSort(array,center + 1, right);
            merge(array, left, center, right);
        }
    }
    private static void merge(int[] array, int left, int center, int right) {
        
        int[] tmpArr = new int[array.length];
        int mid = center + 1;
        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(mid <= right) {
            
            tmpArr[third ++] = array[mid ++];
        }
        while(left <= center) {
            
            tmpArr[third ++] = array[left ++];
        }
        while(tmp <= right) {
            
            array[tmp] = tmpArr[tmp ++];
        }
    }

基数排序

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序

/*
     * 基数排序
     */
    public static void radixSort(int[] array) {
        
        int max = array[0];
        for(int i = 1; i < array.length; i ++) {
            if(array[i] > max) {
                
                max = array[i];
            }
        }
        int time = 0;
        while(max > 0) {
            
            max /= 10;
            time ++;
        }
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for(int i = 0; i < 10; i++) {
            
            ArrayList<Integer> queue1 = new ArrayList<>();
            queue.add(queue1);
        }
        for(int i = 0; i < time; i ++) {
            
            for(int anArray : array) {
                
                int x = anArray % (int)Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(anArray);
                queue.set(x, queue2);
            }
            int count = 0;
            for(int k = 0; k < 10; k ++) {
                
                while(queue.get(k).size() > 0) {
                    
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count ++;
                }
            }
        }
    }

源码

import java.util.ArrayList;
import java.util.Arrays;

public class Sort {
    
    /*
     * 直接插入排序
     */
    public static void insertSort(int[] array) {
        
        for(int i = 1; i < array.length; i++ ) {
            
            int temp = array[i];
            int j = i - 1;
            for(; j >=0; j --) {
                
                if(array[j] > temp)
                    array[j + 1] = array[j];
                else
                    break;
            }
            array[j + 1] = temp;
        }
    }
    /*
     * 希尔排序
     */
    public static void shellSort(int[] array) {
        
        int i, j;
        int temp;
        int gap = 1;
        int len = array.length;
        while(gap < len / 3) {
            
            gap = gap * 3 + 1;
        }
        for(; gap > 0; gap /= 3) {
            
            for(i = gap; i < len; i ++) {
                
                temp = array[i];
                for(j = i - gap; j >=0; j -= gap) {
                    
                    if(array[j] > temp)
                        array[j + gap] = array[j];
                    else
                        break;
                }
                array[j + gap] = temp;
            }
        }
    }
    /*
     * 简单选择排序
     */
    public static void selectSort(int[] array) {
        
        int position = 0;
        for(int i = 0; i < array.length; i ++) {
            
            int temp = array[i];
            int j = i + 1;
            position = i;
            for(; j < array.length; j ++) {
                
                if(array[j] < temp) {
                    
                    temp = array[j];
                    position = j;
                }
            }
            array[position] = array[i];
            array[i] = temp;
        }
    }
    /*
     * 堆排序
     */
    public static void heapSort(int[] array) {
        
        int len = array.length - 1;
        int beginIndex = (len - 1) >> 1;
        for(int i = beginIndex; i >= 0; i --) {
            
            maxHeapify(i, len, array);
        }
        for(int i = len; i > 0; i --) {
            
            swap(0, i, array);
            maxHeapify(0, i - 1, array);
        }
    }
    private static void swap(int i, int j, int[] array) {
        
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    private static void maxHeapify(int index, int len, int[] arr) {
        
        int li = (index << 1) + 1;
        int ri = li + 1;
        int cMax = li;
        if(li > len) {
            
            return;
        }
        if(ri <= len && arr[ri] > arr[li]) {
            
            cMax = ri;
        }
        if(arr[cMax] > arr[index]) {
            
            swap(cMax, index, arr);
            maxHeapify(cMax, len, arr);
        }
    }
    /*
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        
        int temp = 0;
        for(int i = 0; i < array.length - 1; i ++) {
            
            for(int j = 0; j < array.length - 1; j ++) {
                
                if(array[j] > array[j + 1]) {
                    
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
    /*
     * 快速排序
     */
    public static void quickSort(int[] array) {
        
        quickSort(array, 0, array.length - 1);
    }
    private static void quickSort(int[] array, int left, int right) {
        
        if(left >= right)
            return;
        int i = left;
        int j = right;
        int temp = array[left];
        while(i < j) {
            
            while(i < j) {
                if(array[j] >= temp)
                    j --;
                else
                    break;
            }
            array[i] = array[j];
            while(i < j) {
                
                if(array[i] <= temp)
                    i ++;
                else
                    break;
            }
            array[j] = array[i];
        }
        array[i] = temp;
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }
    /*
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        
        mergeSort(array, 0, array.length - 1);
    }
    private static void mergeSort(int[] array, int left, int right) {
        
        if(left < right) {
            
            int center = (left + right) / 2;
            mergeSort(array, left, center);
            mergeSort(array,center + 1, right);
            merge(array, left, center, right);
        }
    }
    private static void merge(int[] array, int left, int center, int right) {
        
        int[] tmpArr = new int[array.length];
        int mid = center + 1;
        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(mid <= right) {
            
            tmpArr[third ++] = array[mid ++];
        }
        while(left <= center) {
            
            tmpArr[third ++] = array[left ++];
        }
        while(tmp <= right) {
            
            array[tmp] = tmpArr[tmp ++];
        }
    }
    /*
     * 基数排序
     */
    public static void radixSort(int[] array) {
        
        int max = array[0];
        for(int i = 1; i < array.length; i ++) {
            if(array[i] > max) {
                
                max = array[i];
            }
        }
        int time = 0;
        while(max > 0) {
            
            max /= 10;
            time ++;
        }
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for(int i = 0; i < 10; i++) {
            
            ArrayList<Integer> queue1 = new ArrayList<>();
            queue.add(queue1);
        }
        for(int i = 0; i < time; i ++) {
            
            for(int anArray : array) {
                
                int x = anArray % (int)Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(anArray);
                queue.set(x, queue2);
            }
            int count = 0;
            for(int k = 0; k < 10; k ++) {
                
                while(queue.get(k).size() > 0) {
                    
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count ++;
                }
            }
        }
    }
    /*
     * 随机数组
     */
    public static int[] randomArray() {
        
        int[] array = new int[10];
        for(int i = 0; i < 10; i++) {
            
            array[i] = (int)(Math.random() * 100);
        }
        return array;
    }
    /*
     * 单元测试
     */
    public static void main(String[] args) {
        
        int[] array = Sort.randomArray();
        Sort.insertSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.shellSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.selectSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.heapSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.bubbleSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.quickSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.mergeSort(array);
        System.out.println(Arrays.toString(array));
        array = Sort.randomArray();
        Sort.radixSort(array);
        System.out.println(Arrays.toString(array));
    }
}

最后编辑于：2017.12.10 05:06:11

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,378评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,356评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,702评论 0赞 342
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,259评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,263评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,036评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,349评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,979评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,469评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,938评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,059评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,703评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,257评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,262评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,485评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,501评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,792评论 2赞 345

常用排序算法

常用排序算法

分类

直接插入排序

希尔排序

简单选择排序

堆排序

冒泡排序

快速排序

归并排序

基数排序

源码

推荐阅读更多精彩内容