常见排序算法(一) 交换排序

1、冒泡排序

• 算法思想

邻位交换
若想升序排序，则将大的数值往后面冒，第一轮排序将最大的交换到数组最后一位，第二轮将次大的交换到数组倒数第二位，依次类推。

• 代码实现

public class BubbleSort
{
    public static int[] bubbleSort(int[] array)
    {
        for(int i = 0; i < array.length - 1; i++)
        {
            for(int j = 0; j < array.length - 1 - i; j++)
            {
                //冒泡排序：通过前后交换的方式将最大的移到最后
                if(array[j] > array[j + 1])
                {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        return array;
    }

    public static void main(String[] args)
    {
        int[] array = new int[]{22,44,77,33,99,66};
        int[] result = bubbleSort(array);
        for(int i = 0; i<result.length;i++)
        {
            System.out.println(result[i]);
        }
    }
}

• 复杂度
  时间复杂度：O(n^2)
  空间复杂度：O(1)
• 稳定性
  相邻元素相等时不会交换，稳定性好。
• 使用场景
  数据量小的情况；基本有序的情况
• 算法改进
  设置标识位，若当前一轮没有发生任何交换，说明该数组已有序，直接退出，不再执行下一轮比较。加上标识位后，可以将最好时间复杂度降为O(n)，初始即为正序情况。

2、快速排序

• 算法思想

分割 + 递归
1、选择一个基准，一般为中间位或者左侧位；
2、左右两侧往中间走，左边遇到比基准大的，右边遇到比基准小的，两者交换；
3、以基准值为界，将数组分为两部分，分别重复步骤1-2

public class QuickSort
{
    public static void quickSort(int[] arr, int low, int high)
    {
        if(low >= high)
        {
            return;
        }
        int i = low;
        int j = high;
        int pivot = arr[(low + high)/2];

        while(i <= j)
        {
            while(arr[i] < pivot)
            {
                i++;
            }
            while(arr[j] > pivot)
            {
                j--;
            }
            if(i < j)
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
            else if(i == j)
            {
                i++;
            }
        }
        quickSort(arr,low,j);
        quickSort(arr,i,high);
    }
    public static void main(String[] args)
    {
        int[] array = new int[]{22,44,77,88,189,22,22,35,666,33,99,66};
        quickSort(array, 0, array.length - 1);
        for(int i = 0; i<array.length;i++)
        {
            System.out.println(array[i]);
        }
    }
}

• 复杂度
  时间复杂度：O(nlogn)

每一次分割后均需遍历所有元素，使用时间O(n)。最好的情况，每次的分割成几乎大小一致的两部分，到达大小为一的数列前，只要做logn次嵌套的调用，调用树的深度是O(logn)；最坏的情况，每次分割1和n-1，退化成冒泡排序时间复杂度变为O(n^2)。

空间复杂度：最坏O(n)，最好O(logn)

• 稳定性
  不稳定
• 使用场景
  数据量大、初始排序随机；基于比较的排序中性能最好。