我的面试准备过程--排序算法(更新中)

摘要：通常情况下，快速排序的时间复杂度为，但在最坏情况下它的时间复杂度会退化至，不过我们可以通过对输入数组进行随机化打乱元素的排列顺序来避免最坏情况的发生。

导师贪腐出逃美国，两年未归，可怜了我。拿了小米和美团的offer，要被延期，offer失效，工作重新找。把准备过程纪录下来，共勉。

最初级

    public void bubbleSort(int[] a){
        int len = a.length;

        for(int i = 0; i < len; i++){
            for(int j = 1; j < len; j++){
                if(a[j - 1] > a[j]){
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }

小优化

    public void bubbleSort(int[] a){
        int len = a.length;

        for(int i = 0; i < len; i++){
            for(int j = 1; j < len - i; j++){
                if(a[j - 1] > a[j]){
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }

大优化，一次冒泡过程没有交换，直接退出排序

    public void bubbleSort(int[] a){
        int len = a.length;

        boolean flag = true;

        while(flag){
            flag = false;
            for(int j = 0; j < len - 1; j++){
                if(a[j] > a[j + 1]){
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
        }
    }

快速排序是目前应用最广泛的排序算法之一，它是一般场景中大规模数据排序的首选，它的实际性能要好于归并排序。通常情况下，快速排序的时间复杂度为O(nlogn)，但在最坏情况下它的时间复杂度会退化至O(n^2)，不过我们可以通过对输入数组进行“随机化”（打乱元素的排列顺序）来避免最坏情况的发生。除了实际执行性能好，快速排序的另一个优势是它能够实现“原地排序”，也就是说它几乎不需要额外的空间来辅助排序。

public static void quickSort(int[] a){
    qSort(a, 0, a.length - 1);
}

private static void qSort(int[] a, int low, int high){
    if(low < high){
        int pivot = partition(a, low, high);
        qSort(a, low, pivot - 1);
        qSort(a, pivot + 1, high);
    }
}

private static void partition(int[] a, int low, int high){
    int pivotValue = a[low];
    while(low < high){
        while(low < high && a[high] >= pivotValue){
            high--;
        }
        a[low] = a[high];
        
        while(low < high && a[low] <= pivotValue){
            low++;
        }
        a[high] = a[low];
    }
    a[low] = pivotValue;
    return low;
}

关于快排的不稳定性

稳定性的概念并不复杂，它只表示两个值相同的元素在排序前后是否有位置变化。如果前后位置变化，则排序算法是不稳定的，否则是稳定的。稳定性的定义符合常理，两个值相同的元素无需再次交换位置，交换位置是做了一次无用功。
两个循环在进行元素比较时，分别用了小于和大于操作（也可以改用小于等于和大于等于，但是对性能没有影响）。这就意味着如果出现和pivot值相同的元素，它都会被作为交换对象而移动到pivot的前面或者后面，这就出现了值相同的元素会交换顺序的问题，因而是不稳定的。

本节参考 http://blog.csdn.net/yutianzu...

快排的优化

优化选取枢轴,优化不必要的交换
三数取中，即取三个关键字先进行排序，将中间数作为枢轴， 一般是取左端、右端和中间三个数， 也可以随机选取。
修改partition算法

private static int partition(int[] a, int low, int high){
    choosePivotValue(a, low, high);
    int pivotValue = a[low];
    
    while(low < high){
        while(low < high && a[high] > pivotValue){
            high--;
        }
        //swap(a,low ,high);交换
        //采用替换而不是交换的方式进行操作
        a[low] = a[high];
        while(low < high && a[low] < pivotValue){
            low++;
        }
        a[high] = a[low];
    }
    a[low] = pivotValue;
    return low;
}

private static void swap(int[] a,int low,int high){
    int temp = a[low];
    a[low] = a[high];
    a[high] = temp;
}
//使中间值处于a[low]的位置
private static void  choosePivotValue(int[] a,int low,int high){
    int mid = (low + high) / 2;
    if(a[low] > a[high]){ // 保证左端较小
        swap(a, low, high);
    }
    if(a[mid] > a[high]){//保证中间较小
        swap(a, mid, high);
    }
    if(a[mid] > a[low]){//保证中间较小
        swap(a, low, mid);
    }
}

优化小数组时的排序方案
快速排序适用于非常大的数组的解决办法， 那么相反的情况，如果数组非常小，其实快速排序反而不如直接插入排序来得更好(直接插入是简单排序中性能最好的)。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势是可以忽略的，但如果数组只有几个记录需要排序时，这就成了大材小用，因此我们需要改进一下 qSort函数。

public static void qSort(int[] a, int low, int high){
    if((high - low) > MAX_LENGTH){
        int pivot = partition(a, low, high);
        qSort(a, low, pivot - 1);
        qSort(a, pivot + 1, high);
    }else{
        insertSort(a);
    }
}

private static void insertSort(int[] a){
    for(int i = 1; i < a.length; i++){
        int key = a[i];
        int j = i - 1;    
        while(j >= 0 && a[j] > key){
            a[j + 1] = a[j];
        }
        a[j + 1] = key;
    }
}

优化递归操作
递归对性能是有一定影响的， qSort 函数在其尾部有两次递归操作。
如果待排序的序列划分极端不平衡，递归深度将趋近与N ，而不是平衡时的 logN,就不仅仅是速度快慢的问题了，栈的大小是很有限的，每次递归调用都会耗费一定的空间 ，函数的参数越多，每次递归耗费的空间也越多。如果能减少递归，将会提高性能。我们对 qSort 实施尾递归优化。

public static void qSort(int[] a, int low, int high){
    if((high - low) > MAX_LENGTH){
        while(low < high){
            int pivot = partition(a, low, high);
            qSort(a, low, pivot - 1);
            low = pivot + 1;
        }
    }else{
        insertSort(a);
    }
}

当我们将 if 改成 while 后，因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1 赋值给low，再循环后，来一次 partition(arr,low,high)时，其效果等同于“qSort(arr, pivot+1, high);”。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。

本节参考 http://blog.csdn.net/scgaligu...

public static void sort(int[] a, int low, int high){
    int mid = (low + high) / 2;
    sort(a, low, mid);
    sort(a, mid + 1, high);
    merge(a, low, mid, high);
}

private static void merge(int[] a, int low, int mid, int high){
    int i = low;
    int j = mid + 1;
    int k = 0;
    int[] temp = new int[high - low + 1];
    
    while(i <= mid && j <= high){
        if(a[i] < a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    
    while(i <= mid){
        temp[k++] = a[i++];
    }
    
    while(j <= high){
        temp[k++] = a[j++];
    }
    
    for(k = 0; k < temp.length; k++){
        a[low + k] = temp[k];
    }
    
}

public static void choseSort(int[] a){
    for(int i = 0; i < a.length; i++){
        int lowIndex = i;
        
        for(int j = i; j < a.length; j++){
            if(a[j] < a[lowIndex]){
                lowIndex = j;
            }
        }
        
        int temp = a[i];
        a[i] = a[lowIndex];
        a[lowIndex] = temp;
    }
}

    public static void insertSort(int[] a){
        for(int i = 1; i < a.length; i++){
            int j = i - 1;
            int key = a[i];
            while(j >= 0 && a[j] > key){
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }

本文参考 http://blog.csdn.net/xsf50717...