[数据结构与算法]排序算法及Java实现总结

库函数API

import java.util.Arrays;

public class Solution {
    public int[] MySort(int[] arr) {
        Arrays.sort(arr);
        return arr;
    }
}

优先队列

import java.util.*;

public class Solution {
   public int[] MySort (int[] arr) {
       Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
           public int compare(Integer a, Integer b) {
               return a-b;
           }
       });
       for(int i=0;i<arr.length;i++){
           queue.add(arr[i]);
       }
       int[] newarr=new int[arr.length];
       for(int i=0;i<arr.length;i++){
           newarr[i]=queue.poll();
       }
       return newarr;
   }
}

单纯三方法

冒泡排序

• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$
• 稳定
• 适用于顺序存储和链式存储的线性表

public class Solution {
    public int[] MySort (int[] arr) {
        for (int i = 0; i < arr.length - 1; ++i) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = true;
                }
            }
            if (flag == false) {
                return arr;
            }
        }
        return arr;
    }
}

直接插入排序

• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$
• 稳定
• 适用于顺序存储和链式存储的线性表

public class Solution {
    public int[] MySort (int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            while (j >= 0 && tmp < arr[j]) {
                arr[j + 1] = arr[j];
                --j;
            }
            arr[j + 1] = tmp;
        }
        return arr;
    }
}

• 时间复杂度$O(n{\log }_{2}n)$
• 空间复杂度$O(1)$
• 稳定
• 仅优化了查找
• 适用于顺序存储线性表

public class Solution {
    public int binarySearchLowBound(int[] array, int low, int high, int target) {
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > target) {
                high = mid;
            } else {
                low = mid + 1; 
            }
        }
        return low;
    }

    public int[] MySort (int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int insert = binarySearchLowBound(arr, 0, i, arr[i]);
            for (int j = i - 1; j >= 0 && j >= insert; j--) {
                arr[j + 1] = arr[j];
            }
            arr[insert] = tmp;
        }
        return arr;
    }
}

简单选择排序

• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$
• 稳定
• 适用于顺序存储和链式存储的线性表

public class Solution {
    public int[] MySort (int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        return arr;
    }
}

单纯的优化

冒泡排序->快速排序

• 时间复杂度$O(n{\log }_{2}n)$，最坏退化为$O(n^2)$
• 空间复杂度$O({\log }_{2}n)$，最坏退化为$O(n)$
• 不稳定
• 适用于顺序存储线性表

public class Solution {
    public int partition(int[] array, int low, int high) {
        int pivot = array[low];
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                --high;
            }
            array[low] = array[high];
            while (low < high && array[low] <= pivot) {
                ++low;
            }
            array[high] = array[low];
        }
        array[low] = pivot;
        return low;
    }

    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivot = partition(array, low, high);
            quickSort(array, low, pivot - 1);
            quickSort(array, pivot + 1, high);
        }
    }

    public int[] MySort (int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }
}

直接插入排序->希尔排序

• 时间复杂度$O(n^{1.3})$，最坏退化为$O(n^2)$
• 空间复杂度$O(1)$
• 不稳定
• 适用于顺序存储的线性表

public class Solution {
    public int[] MySort (int[] arr) {
        for (int d = arr.length; d >= 1; d >>= 1) {
            for (int i = d; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - d;
                while (j >= 0 && tmp < arr[j]) {
                    arr[j + d] = arr[j];
                    j -= d;
                }
                arr[j + d] = tmp;
            }   
        }
        return arr;
    }
}

简单选择排序->堆排序

• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$
• 稳定
• 适用于顺序存储和链式存储的线性表

public class Solution {
    private void maxHeapfy(int[] arr, int i, int heapSize) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, largest, i);
            maxHeapfy(arr, largest, heapSize);
        }
    }

    private void buildMaxHeap(int[] array, int heapSize) {
        for (int i = (heapSize - 2) >> 1; i >= 0; i--) {
            maxHeapfy(array, i, heapSize);
        }
    }

    public void swap(int[] A, int i, int j) {
        if (i != j) {
            A[i] ^= A[j];
            A[j] ^= A[i];
            A[i] ^= A[j];
        }
    }

    public int[] MySort(int[] arr) {
        int length = arr.length;
        buildMaxHeap(arr, length);
        for (int i = 0; i < length; i++) {
            swap(arr, 0, length - 1 - i);
            maxHeapfy(arr, 0, length - i - 1);
        }
        return arr;
    }
}

分治归并

• 时间复杂度$O(n{\log }_{2}n)$
• 空间复杂度$O(n)$
• 稳定

public class Solution {
    public int[] MySort (int[] arr) {
        mergeSort(arr, 0, arr.length);
        return arr;
    }
    // [low, mid) [mid, high)
    public void mergeSort(int[] array, int low, int high) {
        if (high - low > 1) {
            int mid = low + ((high - low) >> 1);
            mergeSort(array, low, mid);
            mergeSort(array, mid, high);
            merge(array, low, mid, high);
        }
    }
    public void merge(int[] array, int low, int mid, int high) {
        int i = low; 
        int j = mid;
        int k = low;

        int[] tmp = new int[array.length];
        while (k < high) {
            tmp[k] = array[k];
            k++;
        }

        k = low;
        while (i < mid && j < high) {
            if (tmp[j] < tmp[i]) {
                array[k++] = tmp[j++];
            } else {
                array[k++] = tmp[i++];
            }
        }

        while (i < mid) {
            array[k++] = tmp[i++];
        }
        while (j < high) {
            array[k++] = tmp[j++];
        }
    }
}