排序算法

常用的排序算法

算法一览

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

优化思路：立一个flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

public int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        boolean flag = true;

        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;

                flag = false;
            }
        }

        if (flag) {
            break;
        }
    }
    return arr;
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

public int[] selectionSort(int[] arr) {
    // 总共要经过 N-1 轮比较
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;

        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j < arr.length; j++)
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 记录目前能找到的最小值元素的下标
            }

        // 将找到的最小下标和i进行交换
        if (i != minIndex) {
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    return arr;
}

插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）（联想打扑克时整理手牌）

优化思路：希尔排序

public int[] insertionSort(int[] arr) {
    // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
    for (int i = 1; i < arr.length; i++) {

        // 当前要插入的数据
        int tmp = arr[i];

        // 从已经排序的序列最右边的开始比较，如果找到比其小的数，把这个数右移一位，腾位置给要插入的数
        int j = i;
        while (j > 0 && tmp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }

        // 存在比其小的数，插入
        if (j != i) {
            arr[j] = tmp;
        }
    }
    return arr;
}

希尔排序

把记录按下标的一定增量（gap）分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序的gap选择与证明是个数学难题，希尔建议的gap是数组长度的一半。

public int[] shellSort(int[] arr) {
    // 初始gap的选择
    int gap = arr.length / 2;

    while (gap > 0) {
        // 从下标为gap的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = gap; i < arr.length; i++) {
            // 当前要插入的数据
            int tmp = arr[i];
            
            // 从已经排序的序列最右边的开始比较，如果找到比其小的数，把这个数右移gap位，腾位置给要插入的数
            int j = i - gap;
            while (j >= 0 && tmp < arr[j]) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap = gap / 2; // gap缩小
    }
    return arr;
}

归并排序

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。设定两个指针分别指向两个已经排序序列的起始位置，不断比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。如果一个序列到达末尾，再把另一个序列的剩余元素添加到合并序列的末尾。

public void mergeSort(int[] result, int[] data, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int mid = left + (right - left) / 2;
    
    // 双指针，确定两个子数组的起始下标
    int ptr1 = left;
    int ptr2 = mid + 1;

    // 分治
    mergeSort(result, data, left, mid);
    mergeSort(result, data, mid+1, right);

    // 按照双指针进行排序
    int index = left;
    while (ptr1 <= mid && ptr2 <= right) {
        result[index++] = data[ptr1] < data[ptr2] ? data[ptr1++] : data[ptr2++];
    }
        
    
    // 两个循环只会执行一个，即：拷贝那个有剩余的数组
    while (ptr1 <= mid) {
        result[index++] = data[ptr1++];
    }
    while (ptr2 <= right) {
        result[index++] = data[ptr2++];
    }

    // 把排好序的结果覆盖掉原始的数组
    for (index = left; index <= right; index++) {
        data[index] = result[index];
    }
}

快速排序

从数列中挑出一个元素，称为 “基准”（pivot）。重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数放到任意一边），这个步骤称为称为分区（partition）操作。递归地把小于基准值元素的子数列和大于基准值元素的子数列都进行排序。

public int partition(int[] data, int left, int right) {
    int pivot = data[left]; // 初始pivot

    // 范围内搜寻比pivot小或大的元素，然后将左侧元素与右侧元素交换
    while (left < right) {
        while (data[right] >= pivot && left < right) {
            right--;
        }
        data[left] = data[right];
        
        while (data[left] <= pivot && left < right) {
            left++;
        }
        data[right] = data[left];
    }

    data[left] = pivot;
    return left;
}

public void quickSort(int[] data, int begin, int end) {
    if (begin >= end) {
        return;
    }

    int pivot = partition(data, begin, end);

    // 两个子数组分治排序
    quickSort(data, begin, pivot - 1);
    quickSort(data, pivot + 1, end);
}

堆排序

创建一个堆 H[0……n-1]，把堆首（最大值）和堆尾互换；把堆的尺寸缩小1，把新的数组顶端数据调整到相应位置；重复步骤2，直到堆的尺寸为1。

public int[] heapSort(int[] arr) {
    int len = arr.length;

    // 构造堆
    for (int i = len / 2; i >= 0; i--) {
        heapify(arr, i, len);
    }

    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i); // 把堆顶最大值和堆尾互换
        len--; // 堆的尺寸减少1
        heapify(arr, 0, len); // 新的堆顶调整到相应位置
    }

    return arr;
}

private void heapify(int[] arr, int i, int len) {
    int left = 2*i + 1, right = 2*i + 2;
    
    // 判断两个儿子是否比当前节点大，如果有，返回最大的那个
    int max = i;
    if (left < len && arr[left] > arr[max]) {
        max = left;
    }
    if (right < len && arr[right] > arr[max]) {
        max = right;
    }

    if (max != i) {
        swap(arr, i, max); // 交换父子
        heapify(arr, max, len); // 调整当前最大节点到堆尾
    }
}

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

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组C中。找出待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，存入数组C的第i项。对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加），将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

private int getMinValue(int[] arr) {
    int minValue = arr[0];
    for (int value : arr) {
        if (minValue > value) {
            minValue = value;
        }
    }

    return minValue;
}

private int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if (maxValue < value) {
            maxValue = value;
        }
    }
         
    return maxValue;
}

private int[] countingSort(int[] arr, int minValue, int maxValue) {
    // 桶的长度
    int bucketLen = maxValue - minValue + 1;
    int[] temp = new int[bucketLen];
    // 每个值映射后出现的次数
    for (int value : arr) temp[value - minValue]++;

    int sortedIndex = 0;
    for (int j = 0; j < bucketLen; j++) {
        while (temp[j] > 0) {
            arr[sortedIndex++] = j + minValue; // 把桶中的数取出放到数组末尾
            temp[j]--; // 用掉了一次当前数，桶中的次数减少
        }
    }

    return arr;
}

PREVIOUSLeetCode 501-600

NEXT系统设计