简单排序

作者: 迷路的丸子 | 来源:发表于2018-09-08 14:07 被阅读0次

常用排序算法（Python实现），持续更新中
基础算法|简单选择排序
选择排序-c语言描述
算法学习之简单排序
排序算法概述
排序
[iOS基础]OC常用算法实现
常用算法OC实现
排序算法的实现
GO语言实现一基本排序

排序是基础的算法问题，常见的排序有插入排序、冒泡排序、快速排序等，它们分别有不同的计算复杂度。插入排序和冒泡排序的复杂度为O(n^2),而快速排序的复杂度为O(nlogn)。因此，快速排序是最常用的排序方法之一，因为它的复杂度更。然而，对简单的排序方法的理解，还是有必要的。

插入排序 (Insert Sort)

插入排序的原理是将乱序的数据依次插入有序的数组中，其中每个数据的插入，都需要遍历一次已排好序的数组，因此会用到两层循环嵌套，复杂度为O(n^2)

InsertSort (from Wikepedia)

插入排序实现方法

public class InsertSort {
    public static int[] isort(int[] num) {
        for (int i = 1; i < num.length; i++) {
            int tmp = num[i];
            int j;
            for (j = i - 1; j >= 0 && tmp < num[j]; j--) {
                num[j+1] = num[j];
            }
            num[j+1] = tmp;
        }
        return num;
    }
}

冒泡排序 (Bubble Sort)

冒泡排序的原理是把乱序数据的最大值（或最小值）依次排到数组边缘，其中每个最大值（或最小值）的排出，都要遍历一次未排好序的数组，因此也会用到两层循环嵌套，复杂度为O(n^2)

BubbleSort (from Wikepedia)

冒泡排序实现方法

public class BubbleSort {
    public static ArrayList<Integer> bsort(ArrayList<Integer> num) {
        for (int i = 0; i < num.size() - 1; i++) {
            for (int j = num.size() - 1; j > i; j--) {
                if (num.get(j) < num.get(j-1)) {
                    int tmp = num.get(j);
                    num.set(j, num.get(j-1));
                    num.set(j-1, tmp);
                }
            }
        }
        return num;
    }
}

快速排序 (Quick Sort)

快速排序是目前最常用的排序方法之一，因其计算效率高，复杂度只有O(nlogn)。它采用了很多巧妙的方法，例如双指针、递归等，其原位排序的特性又极大节省了运算所需的内存空间

快速排序实现方法

public class Sorter {

    public static void qsort(Integer head, Integer tail, ArrayList<Integer> input) {
        if (head >= tail || input.isEmpty() || input.size() <= 1) {
            return;
        }
        int i = head;
        int j = tail;
        
        // 1.任意取一个数，这里取数组中位数下标的对应值
        Integer pivot = input.get((i + j) / 2);
        System.out.print("before qsort:");
        for (int k = head; k <= tail; k++) {
            System.out.print(input.get(k)+" ");
        }
        System.out.print("\n");
        
        // 2.排序，将小于pivot的值放在左边，大于pivot的值放在右边
        while (i <= j) {
            while (input.get(i) < pivot) {
                // 无需变换位置，光标移到后一个位置
                i++;
            }
            
            while (input.get(j) > pivot) {
                // 无需变换位置，光标移到前一个位置
                j--;
            }
            
            if (i < j) {
                // 数据交换，然后继续移动光标
                Integer tmp = input.get(i);
                input.set(i, input.get(j));
                input.set(j, tmp);
                i++;
                j--;
            }
            
            // 必须用else if而不能用if，交换后重新进入循环，否则可能会出现剩下的值卡在中间无法排序的现象
            else if (i == j) {
                System.out.println("i == j");
                i++;                                 // 剩下一个恰好等于pivot的数
            }
        }
        
        // 3.分块,继续排序
        System.out.print("after qsort:");
        for (int k = head; k <= tail; k++) {
            System.out.print(input.get(k)+" ");
        }
        System.out.print("\n\n");

        // 递归继续排序
        qsort(head, j, input);
        qsort(i, tail, input);
    }
}

测试

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(9);
        list.add(7);
        list.add(8);
        list.add(5);
        list.add(7);
        list.add(10);
        list.add(2);
        list.add(4);
        list.add(3);
        list.add(1);
        Sorter.qsort(0, list.size()-1, list);
        System.out.print(list);
    }
}

结果

before qsort:9 7 8 5 7 10 2 4 3 1 
after qsort:1 3 4 5 2 10 7 8 7 9 

before qsort:1 3 4 5 2 
after qsort:1 3 2 5 4 

before qsort:1 3 2 
after qsort:1 2 3 

before qsort:1 2 
i == j
after qsort:1 2 

before qsort:5 4 
after qsort:4 5 

before qsort:10 7 8 7 9 
i == j
after qsort:7 7 8 10 9 

before qsort:7 7 8 
after qsort:7 7 8 

before qsort:7 8 
i == j
after qsort:7 8 

before qsort:10 9 
after qsort:9 10 

[1, 2, 3, 4, 5, 7, 7, 8, 9, 10]