内部排序比较（Java版）

2017-06-21

1 三种基本排序算法
1.1 插入排序
1.2 交换排序（冒泡）
1.3 选择排序（简单）
2 比较
3 补充
3.1 快速排序
3.2 什么是桶排序
3.3 堆排序

1 三种基本排序算法

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

1.2 交换排序（冒泡）

    public static void BubbleSortS(int[] arrs) {
        int tmp;
        for (int i = arrs.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arrs[j] > arrs[j + 1]) {
                    tmp = arrs[j];
                    arrs[j] = arrs[j + 1];
                    arrs[j + 1] = tmp;
                }
            }
        }
    }

1.3 选择排序（简单）

    public static void SelectSort(int[] arrs) {
        int minIndex;
        int tmp;
        for (int i = 0; i < arrs.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arrs.length; j++) {
                if (arrs[minIndex] > arrs[j])
                    minIndex = j;
            }

            if (minIndex != i) {
                tmp = arrs[minIndex];
                arrs[minIndex] = arrs[i];
                arrs[i] = tmp;
            }
        }
    }

2 比较

排序方法	复杂度	辅助空间	内外循环	一次内循环取最大数	一次循环交换次数
插入排序	O(n2)	1	i=1->length-1 j=i-1->0	否	O(1)
冒泡排序	O(n2)	1	i=length-1->1 j=0->i-1	是	O(n)
选择排序	O(n2)	2	i=0->length-1 j=i+1->length-1	是	O(1)

内部排序（C#）

3 补充

3.1 快速排序

快速排序是对冒泡排序的一种改进。

时间复杂度，最坏是O（n2），一般O（nlogn），
空间复杂度（递归实现），在一般情况下的空间复杂度为O（logn），在最差的情况下，若每次只完成了一个元素，那么空间复杂度为O（n）

/**
 * 快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。
 * 时间复杂度，最坏是O（n2），一般O（nlogn）
 */
public class QuickSort
{
    public static void main(String[] args)
    {
        int[] arr=new int[]{1,5,2,3,6,8,4,9,7,5};
        QuickSort quickSort=new QuickSort(arr);
        quickSort.sort();
        quickSort.print();
    }

    private int[] arr;
    public QuickSort(int[] arr)
    {
        this.arr=arr;
    }

    public void sort()
    {
        quickSort(arr,0,arr.length-1);
    }

    public void quickSort(int[] arr,int begin,int end)
    {
        if(begin<end)
        {
            int i = partition(arr, begin, end);
            quickSort(arr,begin,i-1);
            quickSort(arr,i+1,end);
        }
    }

    private int partition(int[] arr, int begin, int end) {
        int key=arr[begin];
        while(begin<end)
        {
            while (begin<end&&arr[end]>=key)end--;
            if(begin<end) {
                arr[begin] = arr[end];
            }
            while(begin<end&&arr[begin]<=key)begin++;
            if(begin<end) {
                arr[end] = arr[begin];
            }
        }
        arr[begin]=key;
        return begin;
    }

    public void print()
    {
        for(int value:arr)
            System.out.println(value);
    }
}

View Code

3.2 什么是桶排序

桶排序，也叫作箱排序，是一个排序算法，也是所有排序算法中最快、最简单的排序算法。其中的思想是我们首先需要知道所有待排序元素的范围，然后需要有在这个范围内的同样数量的桶，接着把元素放到对应的桶中，最后按顺序输出。

时间复杂度为O（n+m）
空间复杂度是O（m），其中m为桶的个数，

/**
 * 桶排序，也叫作箱排序，是一个排序算法，也是所有排序算法中最快、最简单的排序算法。
 * 其中的思想是我们首先需要知道所有待排序元素的范围，然后需要有在这个范围内的同样数量的桶，接着把元素放到对应的桶中，最后按顺序输出。
 * 由于时间复杂度为O（n+m），m为桶容量,如果m比n大太多，则从时间上来说，性能也并不是很好。
 */
public class BucketSort {
    public static void main(String[] args)
    {
        int[] needSortedArr=new int[]{9,2,3,0,3};
        BucketSort bucketSort=new BucketSort(10,needSortedArr);
        bucketSort.sort();
        bucketSort.print();
    }

    private int[] buckets;
    private int[] array;

    public BucketSort(int range,int[] array)
    {
        this.buckets=new int[range];
        this.array=array;
    }

    public void sort()
    {
        if(array!=null&&array.length!=0)
        {
            for(int i=0;i<array.length;i++)
            {
                buckets[array[i]]++;
            }
        }
    }

    public void print()
    {
        for(int i=0;i<buckets.length;i++)
        {
            for(int j=buckets[i];j>0;j--)
                System.out.println(i);
        }
    }
}

View Code

3.3 堆排序

堆的定义

我们可以吧这个序列看成一个二叉树，可得， 1）最大堆的根节点最大，2)上层总比下层大

时间复杂度是O（logn）

public class HeapSort {
    public static void main(String[] args) {
        int[] array = { 8, 6, 9, 7, 5, 4, -3, -2, -1, 0, 1, 2, 3 };

        System.out.println("Before heap:");
        printArray(array);
        printHeapTree(array);

        System.out.println("build max heap:");
        buildMaxHeap(array);
        printArray(array);
        printHeapTree(array);

        heapSort(array);

        System.out.println("After heap sort:");
        printArray(array);
        printHeapTree(array);
    }

    public static void heapSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        //建大顶堆
        buildMaxHeap(array);

        //堆排序
        for (int i = array.length - 1; i >= 1; i--) {
            exchangeElements(array, 0, i);
            maxHeap(array, i, 0);
        }
    }

    private static void buildMaxHeap(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int half = array.length / 2-1;
        for (int i = half; i >= 0; i--) {
            maxHeap(array, array.length, i);
        }
    }

    //时间复杂度O(logN)
    private static void maxHeap(int[] array, int heapSize, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;

        int largest = index;
        if (left < heapSize && array[left] > array[index]) {
            largest = left;
        }

        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }

        if (index != largest) {
            exchangeElements(array, index, largest);
            maxHeap(array, heapSize, largest);
        }
    }

    public static void printArray(int[] array) {
        System.out.print("{");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("}");
    }

    private static void printHeapTree(int[] array)
    {
        for(int i=1;i<array.length;i=i*2)
        {
            for(int k=i-1;k<2*(i)-1&&k<array.length;k++)
            {
                System.out.print(array[k]+" ");
            }
            System.out.println();
        }
    }

    public static void exchangeElements(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}

View Code