常用排序算法

分类

  • 插入排序（直接插入排序、希尔排序）
  • 交换排序（冒泡排序、快速排序）
  • 选择排序（直接选择排序、堆排序）
  • 归并排序
  • 分配排序（基数排序）

所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序、希尔排序、堆排序，直接选择排序

排序分类

直接插入排序

基本思想：在要排序的一组数中，假设前面 (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;
        }
    }

希尔排序

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

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

基本思想：先取一个正整数 d1 < n，把所有相隔 d1 的记录放一组，每个组内进行直接插入排序；然后 d2 < d1，重复上述分组和排序操作；直到 di = 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 个元素的序列（h1,h2,...,hn），当且仅当满足（hi >= h2i,hi >= h2i+1）或（hi <= h2i,hi <= h2i+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));
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容