排序整理

排序算法分内部排序和外部排序。内部排序是把数据记录放在内存中排序，外部排序由于数据量一般较大，内存不够，需要访问外存。

• 内部排序
  • 交换排序
    • 冒泡
    • 快排
  • 插入排序
    • 直接插入
    • 希尔
  • 选择排序
    • 简单选择
    • 堆排
  • 归并排序
  • 基数排序
• 外部排序

“八大排序”即冒泡排序、快速排序、直接插入排序、shell排序、简单选择排序、堆排序、归并排序和基数排序

冒泡排序

public void bubbleSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

快速排序

单线程

public void quickSort(int[] arr, int l, int r) {
    if (arr == null || arr.length == 0) return;
    if (l >= r) return;
    int i = l, j = r;
    int x = arr[l];
    while (i < j) {
        while (i < j && arr[j] >= x) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= x) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = x;
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
}

多线程执行

static class QuickSortTask implements Runnable {

    int[] arr;
    int left;
    int right;

    public QuickSortTask(int[] arr, int left, int right) {
        this.arr = arr;
        this.left = left;
        this.right = right;
    }

    @Override
    public void run() {
        if (arr == null || arr.length == 0) {
            return;
        }
        if (left >= right) {
            return;
        }
        int i = left, j = right;
        int x = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= x) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= x) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = x;
        QuickSortTask quickSortTaskLeft = new QuickSortTask(arr, left, i - 1);
        QuickSortTask quickSortTaskRight = new QuickSortTask(arr, i + 1, right);
        Thread left = new Thread(quickSortTaskLeft);
        Thread right = new Thread(quickSortTaskRight);
        left.start();
        right.start();
        try {
            left.join();
            right.join();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
}

Fork/Join框架

static class QuickSortTask extends RecursiveAction {

    int[] arr;
    int left;
    int right;

    public QuickSortTask(int[] arr, int left, int right) {
        this.arr = arr;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute() {
        if (arr == null || arr.length == 0) {
            return;
        }
        if (left >= right) {
            return;
        }
        int i = left, j = right;
        int x = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= x) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= x) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = x;
        QuickSortTask quickSortTaskLeft = new QuickSortTask(arr, left, i - 1);
        QuickSortTask quickSortTaskRight = new QuickSortTask(arr, i + 1, right);
        invokeAll(quickSortTaskLeft, quickSortTaskRight);
    }
}

直接插入排序

void insertSort(int[] arr) {
    int temp = 0, j = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            temp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = temp;
        }
    }
}

选择排序

void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

归并排序

int[] mergeSort(int[] arr, int left, int right) {
    if (left == right) {
        return new int[]{arr[left]};
    }
    int mid = left + right >> 1;
    return mergeTwoArray(mergeSort(arr, left, mid), mergeSort(arr, mid + 1, right));
}

int[] mergeTwoArray(int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    int[] res = new int[left.length + right.length];
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            res[k++] = left[i++];
        } else {
            res[k++] = right[j++];
        }
    }
    while (i < left.length) {
        res[k++] = left[i++];
    }
    while (j < right.length) {
        res[k++] = right[j++];
    }
    return res;
}

堆排序

以大根堆为例：

void heapSort(int[] arr) {
    int len = arr.length;
    buildMaxHeap(arr, len);
    for (int i = len - 1; i > 0; i--) {
        swap(arr, i, 0);
        len--;
        adjustHeap(arr, 0, len);
    }
}

void buildMaxHeap(int[] arr, int len) {
    for (int i = len >> 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
}

void adjustHeap(int[] arr, int i, int len) {
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int max = i;
    if (left < len && arr[left] > arr[max]) {
        max = left;
    }
    if (right < len && arr[right] > arr[max]) {
        max = right;
    }
    if (i != max) {
        swap(arr, i, max);
        adjustHeap(arr, max, len);
    }
}

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