排序算法代码整理

注：以下均为升序排序；

简单排序：

冒泡排序：相邻的元素两两比较，将最大的数放在右边。

int n;
long[] theArray = new long[n];
public void bubbleSort(){
    for (int out = n-1 ; out > 1 ; out--){
        for (int in = 0 ; in < out ; in++){
            if (theArray[in] > theArray[in+1]){
                swap(in,in+1);
            }
        }
    }
}
public void swap(int x,int y){
    long temp = theArray[x];
    theArray[x] = theArray[y];
    theArray[y] = temp;
}

选择排序：选定第一个元素暂且认为是最小的，依次与剩下的元素比较有比其小的则交换，再交换到第一个位置；然后再定义第二个为次最小的重复上述步骤；

public void selectSort(){
    for (int out = 0 ; out < n-1 ; out ++){
        int min = out ;
        for (int in = out + 1 ; in < n ; in++){
            if (theArray[in] < theArray[min]){
                min = in;
            }
            swap(min,out);
        }
    }
}

        选择排序和冒泡排序的比较次数是一样的都是n的平方次，但是选择排序的交换次数要比冒泡排序的交换次数少。选择排序最大的交换次数为n-1，冒泡排序交换的最大次数为（n-1）！次，所以在n很大的时候选择选择排序，在n很小的时候，如果比较的时间级比交换的时间级小也可以选择选择排序。

插入排序：插入排序适合待排序数组中有一部分已经是有序的数组，找到没有序的边界后，将其依次的向前（后）交换到左边大（小）右边小（大）的位置，复制的次数太多了，才能找到暂时的正确位置。

public void insertSort(){
    for (int out = 1 ; out < n ; out++){
        long temp = theArray[out];
        int in = out;
        while(in >0 && theArray[in-1] > temp){
            theArray[in] = theArray[in-1];
            --in;
        }
        theArray[in] = temp;
    }
}

归并排序：现将待排序的数组从中间划分成两部分，然后递归将原数组一直到划分为每个数组只有一个元素或两个元素，再依次将划分好的数组两两有序的合并到一个数组，直到全部有序的合并。

public void mergeSort(){
    long[] workSpace = new long[n];
    recMergeSort(workSpace,0,n-1);
}
public void recMergeSort(long[] workSpace,int lowerBound,int upperBound){
    int mid = (lowerBound + upperBound)/2;
    recMergeSort(workSpace,lowerBound,mid);//递归
    recMergeSort(workSpace,mid+1,upperBound);
    merge(workSpace,lowerBound,mid+1,upperBound);//合并
}
public void merge(long[] workSpace,int lowerPtr,int highPtr,int upperBound){
    int lowerBound = lowerPtr;
    int mid = highPtr - 1;
    int n = lowerBound + upperBound -1;
    int j =0;
    while(lowerPtr <= mid && highPtr <= upperBound){
        if (theArray[lowerPtr] < theArray[highPtr]){
            workSpace[j++] = theArray[lowerPtr++];
        }
        else {
            workSpace[j++] = theArray[highPtr++];
        }
    }
    while(lowerPtr <= mid){
        workSpace[j++] = theArray[lowerPtr++];//中后半部分比中前半部分短
    }
    while (highPtr <= upperBound){
        workSpace[j++] = theArray[highPtr++];//中前半部分比中后半部分短

    }
    for (int i = 0 ; i < n ; i++){
        theArray[lowerBound+i] = workSpace[i];
    }
}

高级排序：

希尔排序：原理与插入排序一致，不同点就是增加一个间隔序列h=h*3+1（1，4，13，40，121，364...)。

public void shellSort(){
    int h = 1;
    while(h <= n/3){
        h = h*3 +1;
    }
    while(h > 0){
        for (int out = h ;out < n ; out++){
            long temp = theArray[out];
            int in = out;
            while(in > h-1 && theArray[in-h] > temp){
                theArray[in] = theArray[in-h];
                in-=h;
            }
            theArray[in] = temp;
        }
        h = (h-1)/3;
    }
}

快速排序：将待排序的数组，划分成一边是比选出来的比较值小（大）一边是比比较值小（大），依次采用递归的方式最后为有序的数组。

public void quickSort(){
    recQuickSort(0,n-1);
}
public void recQuickSort(int left,int right){
    int size = left + right - 1;
    if (size <= 3){
        manualSort(left,right);//选用“三个数据项取中”的方式选出一个比较值，是了避免选中的比较值太小或太大；
    }
    else{
        long media = medianOf3(left,right);
        int partition = partitionIt(left,right,media);
        recQuickSort(left,partition);
        recQuickSort(partition+1,right);
    }
}

public int partitionIt(int left,int right,long media){
    int leftPtr = left -1;
    int rightPtr = right;
    while(true){
        while (theArray[++leftPtr] < media);
        while (theArray[--rightPtr] > media);
        if (leftPtr >= rightPtr){
            break;
        }else{
        swap(leftPtr,rightPtr);
        }
    }
    swap(leftPtr,right);
    return leftPtr;
}

public long medianOf3(int left,int right){
    int mid = (left+right)/2;
    if (theArray[left] > theArray[mid]){
        swap(left,mid);
    }
    if (theArray[mid] > theArray[right]){
        swap(mid,right);
    }
    if (theArray[left] > theArray[right]){
        swap(left,right);
    }
    swap(mid,right);
    return theArray[right];
}

public void manualSort(int left, int right){
    int size = left + right - 1;
    if (size <= 1){
        return;
    }
    if (size ==2){
        if (theArray[left] > theArray[right]){
            swap(left, right);
        }
        return;
    }
    else{
        if (theArray[left] > theArray[right - 1]) {
            swap(left, right -1);
        }
        if (theArray[left] > theArray[right]){
            swap(left, right);
        }
        if (theArray[right - 1] > theArray[right]) {
            swap(right-1,right);
        }
    }
}

堆排序：

根据初始数组构造大顶堆（大顶堆：每个节点的关键字大于等于子节点的关键字，升序采用大顶推；小顶堆：每个节点的关键字小于等于子节点的关键字，降序采用小顶推）；

每次交换大顶堆的第一个和最后一个元素，推出最后一个元素，然后把剩下的元素重新调整为大顶堆。

public void HeapAdjust(int[] array, int parent, int length) {
    int temp = array[parent]; // temp保存当前父节点
    int child = 2 * parent + 1; // 先获得左孩子
    while (child < length) {
        if (child + 1 < length && array[child] < array[child + 1]) {
            child++;// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
        }
        if (temp >= array[child])// 如果父结点的值已经大于孩子结点的值，则直接结束
            break;
        array[parent] = array[child];// 把孩子结点的值赋给父结点
        parent = child;// 选取孩子结点的左孩子结点,继续向下筛选
        child = 2 * child + 1;
    }
    array[parent] = temp;
}
public void heapSort(int[] list) {
    for (int i = list.length / 2; i >= 0; i--) {// 循环建立初始堆
        HeapAdjust(list, i, list.length - 1);
    }
    for (int i = list.length - 1; i > 0; i--) {
        int temp = list[i]; // 最后一个元素和第一元素进行交换
        list[i] = list[0];
        list[0] = temp;
        HeapAdjust(list, 0, i);// 筛选 R[0] 结点，得到i-1个结点的堆
    }
}

各种排序的时间复杂度与空间复杂度：