2019-08-02-排序算法.md

layout	title	date	categories	tags	series	series_index	comments	copyrights	mathjax
post	排序算法	2019-08-02 00:00:00 +0800	算法	qsort sort	算法笔记	1	true	原创	true

冒泡排序

冒泡排序从前往后遍历数组，每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换两者的位置。

每遍历一轮，最大的元素就会被“冒泡”到最后。

public class Sort {
    public static <T extends Comparable<T>> void bubbleSort(T[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 遍历的第 i 轮，需要确定第 n - 1 - i 个元素
            for (int j = 0; j < n - 1 - i; j++) {
                // 最后 i 个元素已经排好序
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

template<std::totally_ordered T>
void bubbleSort(std::vector<T>& arr) {
    for (size_t i = 0; i < arr.size() - 1; i++) {
        for (size_t j = 0; j < arr.size() - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

选择排序

选择排序从前往后遍历数组，每次找到最小的元素，将其放到当前遍历的位置。

public class Sort {
    public static <T extends Comparable<T>> void selectSort(T[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 遍历的第 i 轮，需要确定第 i 个元素
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                // 在 i 之后寻找最小的元素
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

template<std::totally_ordered T>
void selectSort(std::vector<T>& arr) {
    for (size_t i = 0; i < arr.size() - 1; i++) {
        size_t minIndex = i;
        for (size_t j = i + 1; j < arr.size(); j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        std::swap(arr[i], arr[minIndex]);
    }
}

插入排序

插入排序时，对于一个待排序的序列，从第一个元素开始，依次将每个元素插入到前面已经排好序的序列中，直到所有元素都排好序。

插入时，采用从后向前的方式，依次比较当前元素和前一个元素的大小关系，如果当前元素小于前一个元素，则交换两者的位置。

public class Sort {
    public static <T extends Comparable<T>> void insertSort(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 让 0 - i 的元素有序
            for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
                // 向前寻找第一个比当前元素小的元素
                swap(arr, j, j - 1);
            }
        }
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

template<std::totally_ordered T>
void insertSort(std::vector<T>& arr) {
    for (size_t i = 1; i < arr.size(); i++) {
        for (size_t j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            std::swap(arr[j], arr[j - 1]);
        }
    }
}

希尔排序

希尔排序是插入排序的改进版，采用分组的方式，将待排序的序列分成若干个子序列，对每个子序列进行插入排序，最后再对整个序列进行一次插入排序。

public class Sort {
    public static <T extends Comparable<T>> void shellSort(T[] arr) {
        int gap = arr.length / 2;
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j >= gap && arr[j].compareTo(arr[j - gap]) < 0; j -= gap) {
                    swap(arr, j, j - gap);
                }
            }
            gap /= 2;
        }
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

template<std::totally_ordered T>
void shellSort(std::vector<T>& arr) {
    for (size_t gap = arr.size() / 2; gap > 0; gap /= 2) {
        for (size_t i = gap; i < arr.size(); i++) {
            for (size_t j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
                std::swap(arr[j], arr[j - gap]);
            }
        }
    }
}

堆排序

堆排序是选择排序的改进版，采用堆的方式，将待排序的序列构建成一个大顶堆或小顶堆，然后依次将堆顶元素取出，放到已排序序列的末尾。

public class Sort {
    public static <T extends Comparable<T>> void heapSort(T[] arr) {
        int n = arr.length;
        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 依次取出堆顶元素
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    public static <T> void heapify(T[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left].compareTo(arr[largest]) > 0) {
            largest = left;
        }
        if (right < n && arr[right].compareTo(arr[largest]) > 0) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

template<std::totally_ordered T>
void heapify(std::vector<T>& arr, size_t n, size_t i) {
    size_t largest = i;
    size_t left = 2 * i + 1;
    size_t right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

template<std::totally_ordered T>
void heapSort(std::vector<T>& arr) {
    for (size_t i = arr.size() / 2 - 1; i < arr.size(); i--) {
        heapify(arr, arr.size(), i);
    }
    for (size_t i = arr.size() - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

快速排序

快速排序是分治法的经典应用，采用递归的方式，将待排序的序列分成两个子序列，对每个子序列进行快速排序，最后将两个子序列合并。

public class Sort {
    public static <T extends Comparable<T>> void quickSort(T[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static <T> void quickSort(T[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static <T> int partition(T[] arr, int low, int high) {
        T pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j].compareTo(pivot) <= 0) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

template<std::totally_ordered T>
size_t partition(std::vector<T>& arr, size_t low, size_t high) {
    T pivot = arr[high];
    size_t i = low - 1;
    for (size_t j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

template<std::totally_ordered T>
void quickSort(std::vector<T>& arr, size_t low, size_t high) {
    if (low < high) {
        size_t pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

template<std::totally_ordered T>
void quickSort(std::vector<T>& arr) {
    quickSort(arr, 0, arr.size() - 1);
}

归并排序

归并排序是分治法的经典应用，采用递归的方式，将待排序的序列分成两个子序列，对每个子序列进行归并排序，最后将两个子序列合并。

public class Sort {
    public static <T extends Comparable<T>> void mergeSort(T[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    public static <T> void mergeSort(T[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

    public static <T> void merge(T[] arr, int low, int mid, int high) {
        T[] temp = Arrays.copyOfRange(arr, low, high + 1);
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            if (i > mid) {
                arr[k] = temp[j++];
            } else if (j > high) {
                arr[k] = temp[i++];
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i++];
            } else {
                arr[k] = temp[j++];
            }
        }
    }
}

template<std::totally_ordered T>
void merge(std::vector<T>& arr, size_t low, size_t mid, size_t high) {
    std::vector<T> temp(arr.begin() + low, arr.begin() + high + 1);
    size_t i = low;
    size_t j = mid + 1;
    for (size_t k = low; k <= high; k++) {
        if (i > mid) {
            arr[k] = temp[j++];
        } else if (j > high) {
            arr[k] = temp[i++];
        } else if (temp[i] <= temp[j]) {
            arr[k] = temp[i++];
        } else {
            arr[k] = temp[j++];
        }
    }
}

template<std::totally_ordered T>
void mergeSort(std::vector<T>& arr, size_t low, size_t high) {
    if (low < high) {
        size_t mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

template<std::totally_ordered T>
void mergeSort(std::vector<T>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

基数排序

基数排序是非比较排序的一种，采用分组的方式，将待排序的序列分成若干个子序列，对每个子序列进行计数排序，最后将所有子序列合并。

public class Sort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    public static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        Arrays.fill(count, 0);
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        System.arraycopy(output, 0, arr, 0, n);
    }
}

void countingSort(std::vector<int>& arr, size_t exp) {
    std::vector<int> output(arr.size());
    std::vector<int> count(10);
    std::fill(count.begin(), count.end(), 0);
    for (size_t i = 0; i < arr.size(); i++) {
        count[(arr[i] / exp) % 10]++;
    }
    for (size_t i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (size_t i = arr.size() - 1; i < arr.size(); i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    std::copy(output.begin(), output.end(), arr.begin());
}

void radixSort(std::vector<int>& arr) {
    int max = *std::max_element(arr.begin(), arr.end());
    for (size_t exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}