排序算法总结

排序算法：

稳定：如果a在b前面 ，并且a==b，排序后a仍在b前面

不稳定：如果a在b前面，并且a==b，排序后a可能在b后面

时间复杂度：指执行当前算法所消耗的时间

空间复杂度：值执行当面算法所占用的内存空间

内排序：所有排序操作都在内存中完成

外排序：数据放在磁盘中，排序通过磁盘和内存的数据传输进行

冒泡排序:

public class bubbleS {
    public static void bubbleSort1(int[] data){
        int len = data.length;
        for(int i=len-1;i>0;i--){
            for(int j=0;j<i;j++){
                //比较相邻两数，若前面大则交换
                if(data[j]>data[j+1]){
                    int tem = data[j];
                    data[j]=data[j+1];
                    data[j+1]=tem;
                }
            }
        }
    }

    public static void bubbleSort2(int[] data){
        int len = data.length;
        for(int i=len-1;i>0;i--){
            //改进冒泡，如果一次比较都没有交换，则已经排好序，跳出循环
            boolean isSort = true;
            for(int j=0;j<i;j++){
                if(data[j]>data[j+1]){
                    int tem = data[j];
                    data[j]=data[j+1];
                    data[j+1]=tem;
                    isSort=false;
                }
            }
            if(isSort) break;
        }
    }
}

选择排序：

public class selectS {
    public static void selectSort1(int[] data){
        for(int i=0;i<data.length;i++){
            //记录每次循环中最小数的下标然后和data[i]交换
            int minIndex = i;
            for(int j=i+1;j<data.length;j++){
                minIndex = data[j]<data[minIndex] ? j : minIndex;
            }
            int tem = data[i];
            data[i]=data[minIndex];
            data[minIndex]=tem;
        }
    }
}

插入排序：

public class insertS {
    public static void insertSort1(int[] data){
        int len = data.length;
        for(int i=1;i<len;i++){//默认第一个数已排好序，从第二个数开始扫描
            int tem = data[i];
            int j = i-1;//将data[i]与前一位data[i-1]比较
            while (j>=0 && tem<data[j]){//若小于，将前面的数往后移
                data[j+1]=data[j];
                j--;
            }
            data[j+1]=tem;//找到位置后插入
        }
    }
}

希尔排序：

public class shellS {
    public static void shellSort1(int[] data){
        int len = data.length;
        int gap = len/2;
        while (gap>0){
            for(int i=gap;i<len;i++){
                int tem = data[i];
                int preIndex = i-gap;
                while (preIndex >= 0 && data[preIndex]>tem){
                    data[preIndex+gap]=data[preIndex];
                    preIndex-=gap;
                }
                data[preIndex+gap]=tem;
            }
            gap/=2;
        }
    }
}

归并排序：

public class mergeS {
    public static void mergeSort1(int[] data){
        if(data==null || data.length==0) return;
        mergeRec(data , 0 , data.length-1);
    }

    public static void mergeRec(int[] data , int left , int right){
        if(left>=right) return;
        int mid = left + (right-left)/2;
        mergeRec(data , left , mid);
        mergeRec(data , mid+1 , right);
        merge(data , left , mid , right);
    }

    public static void merge(int[] data , int left , int mid , int right){
        int[] h = new int[right-left+1];
        int p1 = left , p2=mid+1;
        int k = 0;
        while (p1<=mid && p2<=right){
            h[k++]=data[p1]<=data[p2] ? data[p1++] : data[p2++];
        }
        while (p1<=mid){
            h[k++]=data[p1++];
        }
        while (p2<=right){
            h[k++]=data[p2++];
        }
        for(int i=0;i<k;i++){
            data[left+i]=h[i];
        }
    }
}

堆排序：

public class heapS {
    public static void heapSort1(int[] data){
        if(data==null || data.length<=1) return;
        for(int i=0;i<data.length;i++){
            siftUp(data , i);//上浮建堆
        }
        int len = data.length-1;
        swap(data , 0 , len);
        while (len>0){
            siftDown(data , 0 , len);
            swap(data , 0 , --len);
        }
    }

    public static void siftUp(int[] data , int i){
        while (data[i]>data[(i-1)/2]){
            swap(data , i , (i-1)/2);
            i=(i-1)/2;
        }
    }

    public static void siftDown(int[] data , int i , int heapSize){
        int left = 2*i+1;
        int right = 2*i+2;
        int maxIdx = i;
        if(left<heapSize && data[left]>data[maxIdx]) maxIdx=left;
        if(right<heapSize && data[right]>data[maxIdx]) maxIdx = right;
        if(maxIdx != i){
            swap(data , i , maxIdx);
            siftDown(data , maxIdx , heapSize);
        }
    }

    public static void swap(int[] data , int s1 , int s2){
        int tem = data[s1];
        data[s1]=data[s2];
        data[s2]=tem;
    }
}

快速排序：

public class quickS {
    public void quickSort_1(int[] data, int start, int end) {
        if (data == null || start < 0 || end > data.length - 1) {
            throw new IllegalArgumentException("Invalid Parameters");
        }
        if (start == end) return;
        int index = partition(data, start, end);
        if (index > start) {
            quickSort_1(data, start, index - 1);
        }
        if (index < end) {
            quickSort_1(data, index + 1, end);
        }
    }

    private int partition(int[] data, int start, int end) {
        int index = start + (int)(Math.random() * (end - start + 1));
        swap(data, index, end);
        int small = start - 1;
        for (index = start; index < end; index++) {
            if (data[index] < data[end]) {
                small++;
                if (small != index) {
                    swap(data, index, small);
                }
            }
        }
        swap(data, small + 1, end);
        return small + 1;
    }

    private void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public void quickSort_2(int[] data, int start, int end) {
        if (data == null || start >= end) return;
        int i = start, j = end;
        int pivotKey = data[start];
        while (i < j) {
            while (i < j && data[j] >= pivotKey) j--;
            if (i < j) data[i++] = data[j];
            while (i < j && data[i] <= pivotKey) i++;
            if (i < j) data[j--] = data[i];
        }
        data[i] = pivotKey;
        quickSort_2(data, start, i - 1);
        quickSort_2(data, i + 1, end);
    }
}