Java实现各种常用的排序算法

Java实现各种常用的排序算法，包括：冒泡排序、插入排序、二分排序、选择排序、希尔排序、堆排序、快速排序（两种写法）、归并排序、基数排序和计数排序（两种写法）。

1. 冒泡排序

    /**
     * 冒泡排序(大的值从前往后冒泡）
     * 优点：稳定排序；适用于数组存储的数据和链表存储的数据；
     */
    public static int[] bubbleSort(int[] a) {
        for (int end = a.length - 1; end > 0; end--) {
            boolean flag = false; //增加一个判断是否发生过交换的标记
            for (int j = 0; j < end; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    flag = true;
                }
            }
            if (!flag) { //如果扫描一遍发现没有发生交换则说明序列已经有序，退出循环
                break;
            }
        }
        return a;
    }
   
    /**
     * 冒泡排序（小的值从后往前下沉）
     * 优点：稳定排序；适用于数组存储的数据和链表存储的数据；
     */
    public static int[] bubbleSort2(int[] a) {
        for (int start = 0; start < a.length - 1; start++) {
            boolean flag = false; //增加一个判断是否发生过交换的标记
            for (int j = a.length - 1; j > start; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, j, j - 1);
                    flag = true;
                }
            }
   
            if (!flag) { //如果扫描一遍发现没有发生交换则说明序列已经有序，退出循环
                break;
            }
        }
        return a;
    }
   

2. 插入排序

    /**
     * 插入排序
     */
    public static int[] insertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i;
            while (j > 0 && temp < a[j - 1]) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
        }
        return a;
    }
   

3. 二分排序

    /**
     * 二分排序
     * 也称折半插入排序，查找次数为O(n log n)，移动次数为O(n^2)
     * Time complexity: O(n^2)
     * 稳定性：稳定排序
     */
    public static int[] binarySort(int[] a) {
        int i, j;
        int low, high, mid;
        int temp;
        for (i = 1; i < a.length; i++) {
            temp = a[i];
            low = 0;
            high = i - 1;
            while (low <= high) {
                mid = (low + high) / 2;
                if (a[mid] > temp) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for (j = i - 1; j > high; j--) {
                a[j + 1] = a[j];
            }
            a[high + 1] = temp;
        }
        return a;
    }
   

4. 选择排序

    /**
     * 选择排序
     */
    public static int[] selectionSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    swap(a, i, j);
                }
            }
            System.out.println(Arrays.toString(a));
        }
        return a;
    }
   

5. 希尔排序

    /**
     * 希尔排序
     */
    public static int[] shellSort(int[] a) {
        int gap = a.length / 2;
        while (gap >= 1) {
            for (int i = gap; i < a.length; i++) {
                int j;
                int temp = a[i];
                for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {
                    a[j + gap] = a[j];
                }
                a[j + gap] = temp;
            }
            gap /= 2;
        }
        return a;
    }
   

6. 堆排序

    /**
     * 堆排序
     */
    public static int[] heapSort(int[] a) {
        buildMaxHeap(a, a.length - 1);
        swap(a, 0, a.length - 1);
        for (int i = 1; i < a.length - 1; i++) {
            adjustMaxHeap(a, 0, a.length - 1 - i);
            swap(a, 0, a.length - 1 - i);
        }
        return a;
    }
   
    public static void buildMaxHeap(int[] data, int lastIndex) {
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            adjustMaxHeap(data, i, lastIndex);
        }
    }
   
    public static void adjustMaxHeap(int[] data, int parent, int lastIndex) {
        /*
         * 通常堆是通过一维数组来实现的。在数组起始位置为 0 的情形中：
         * 父节点 i 的左子节点在位置 (2*i+1);
         * 父节点 i 的右子节点在位置 (2*i+2);
         * 子节点 i 的父节点在位置 floor((i-1)/2);
         */
        while (2 * parent + 1 <= lastIndex) {
            int maxChildIndex = 2 * parent + 1;
   
            // 如果当前左孩子不是末尾元素
            if (maxChildIndex < lastIndex) {
   
                // 如果左孩子小于右孩子,取右孩子下标
                if (data[maxChildIndex] < data[maxChildIndex + 1]) {
   
                    maxChildIndex++;
                }
            }
   
            // 比较当前父节点和最大孩子节点
            if (data[parent] < data[maxChildIndex]) {
                swap(data, parent, maxChildIndex);
                parent = maxChildIndex;
            } else {
                break;
            }
        }
    }
   
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
   

7. 快速排序

    /**
     * 快速排序
     */
    public static int[] quickSort(int[] a) {
        if (a.length > 0) {
            quickSortRecursion(a, 0, a.length - 1);
        }
        return a;
    }
   
    public static void quickSortRecursion(int[] data, int low, int high) {
        if (low < high) {
            int middle = partition(data, low, high);
            quickSortRecursion(data, low, middle - 1);
            quickSortRecursion(data, middle + 1, high);
        }
    }
   
    public static int partition(int[] data, int low, int high) {
        int temp = data[low]; // 数组的第一个作为中轴
        while (low < high) {
            while (low < high && data[high] >= temp) {
                high--;
            }
            data[low] = data[high]; // 比中轴小的记录移到低端
            while (low < high && data[low] <= temp) {
                low++;
            }
            data[high] = data[low]; // 比中轴大的记录移到高端
        }
        data[low] = temp;
        return low; // 返回中轴的位置
    }
   
    /**
     * 快速排序的第二种写法
     */
    public static int[] quickSort2(int[] a) {
        qSort(a, 0, a.length - 1);
        return a;
    }
   
    public static void qSort(int[] sequence, int low, int high) {
        int pivot = sequence[low]; // 取首元素的为基准
        int left = low, right = high;
        if (low >= high) {
            return;
        }
        swap(sequence, low, high); //将基准与最后一个元素交换
        while (true) {
            //将序列中比基准小的移到基准左边，比基准大的移到基准右边
            while (low < high && sequence[low] <= pivot) {
                low++;
            }
            while (low < high && sequence[high] >= pivot) {
                high--;
            }
            if (low < high) {
                swap(sequence, low, high);
            } else {
                break;
            }
        }
        swap(sequence, low, right); //将最后的基准换到正确的位置
   
        //分别对两个子集进行快排
        qSort(sequence, left, low - 1);
        qSort(sequence, low + 1, right);
    }
   

8. 归并排序

    /**
     * 归并排序
     */
    public static int[] mergingSort(int[] a) {
        if (a.length > 0) {
            mergingSortRecursion(a, 0, a.length - 1);
        }
        return a;
    }
   
    public static void mergingSortRecursion(int[] data, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergingSortRecursion(data, left, middle);
            mergingSortRecursion(data, middle + 1, right);
            merge(data, left, middle, right);
        }
    }
   
    public static void merge(int[] data, int left, int middle, int right) {
        int[] tempArray = new int[data.length];
        int i = left; // 左边序列的游标
        int j = middle + 1; // 右边序列的游标
        int k = left; // 临时序列的游标
   
        // 从两个数组中取出最小的放入中间数组
        while (i <= middle && j <= right) {
            if (data[i] <= data[j]) {
                tempArray[k++] = data[i++];
            } else {
                tempArray[k++] = data[j++];
            }
        }
   
        // 剩余部分依次放入中间数组
        while (j <= right) {
            tempArray[k++] = data[j++];
        }
        while (i <= middle) {
            tempArray[k++] = data[i++];
        }
   
        // 将中间数组中的内容复制回原数组
        while (left <= right) {
            data[left] = tempArray[left++];
        }
    }
   

9. 基数排序

    /**
     * 基数排序
     */
    public static int[] radixSort(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            max = a[i] > max ? a[i] : max;
        }
   
        int time = 0;
        while (max > 0) {
            time++;
            max /= 10;
        }
   
        List<ArrayList<Integer>> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            queue.add(new ArrayList<>());
        }
   
        for (int i = 0; i < time; i++) {
            // 按某位对原数组进行一趟排序
            for (int j = 0; j < a.length; j++) {
                int d = a[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> list = queue.get(d);
                list.add(a[j]);
                queue.set(d, list);
            }
   
            // 把queue进行过一趟排序的数据拷贝回原数组
            int count = 0;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    a[count] = queue.get(k).get(0);
                    queue.get(k).remove(0);
                    count++;
                }
            }
        }
        return a;
    }
   

10. 计数排序

     /**
      * 计数排序法1 取出序号用了少量的比较和循环
      */
     public static int[] countingSort1(int[] a) {
         int max = 0;
         for (int i = 0; i < a.length; i++) {
             max = a[i] > max ? a[i] : max;
         }
         int[] count = new int[max + 1];
         for (int i = 0; i < a.length; i++) {
             count[a[i]]++;
         }
         int sum = 0;
         for (int i = 0; i < count.length; i++) {
             if (count[i] > 0) {
                 for (int j = 0; j < count[i]; j++) {
                     a[sum + j] = i;
                 }
             }
             sum += count[i];
         }
         return a;
     }
    
     /**
      * 计数排序法2 完全没有使用比较和循环
      */
     public static int[] countingSort2(int[] a) {
         int max = 0;
         for (int i = 0; i < a.length; i++) {
             max = a[i] > max ? a[i] : max;
         }
         int[] count = new int[max + 1];
    
         for (int i = 0; i < a.length; i++) {
             count[a[i]]++;
         }
    
         for (int i = 1; i < count.length; i++) {
             count[i] += count[i - 1];
         }
    
         int[] b = new int[a.length];
         for (int i = 0; i < a.length; i++) {
             b[count[a[i]] - 1] = a[i];
             count[a[i]]--;
         }
         return b;
     }
    

各个方法的测试代码实现如下：

    public static void main(String[] args) {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35,
                25, 53, 51};
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(binarySort(a)));
    }

运行结果如下：

[49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51]
[4, 5, 12, 13, 15, 17, 18, 23, 25, 27, 34, 34, 35, 38, 49, 49, 51, 53, 54, 56, 62, 64, 65, 76, 78, 97, 98, 99]

Process finished with exit code 0

注：简书使用Markdown语言编辑文本时，感觉复制代码调格式很麻烦。