常见的排序算法
2019-02-13 本文已影响0人
Baltan
冒泡排序
public class BubbleSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
int arrLength = arr.length;
/**
* 先以第一个数字为终点，从尾部开始，每两个相邻的数字相互比较，如果前面的数字大于后面的数字就交换两数，
* 循环结束后，第一个位置上为最小的数字。
* 再以第二个数字为终点，从尾部开始，每两个相邻的数字相互比较，如果前面的数字大于后面的数字就交换两数，
* 循环结束后，第二个位置上为第二小的数字。
* 直到以倒数第二个数字为基准，和最后一个数字比较交换完成即可。
*
* 49, 38, 65, 97, 76, 13
* 49, 38, 65, 97, 13, 76
* 49, 38, 65, 13, 97, 76
* 49, 38, 13, 65, 97, 76
* 49, 13, 38, 65, 97, 76
* 13, 49, 38, 65, 97, 76
*
* 13, 49, 38, 65, 76, 97
* 13, 38, 49, 65, 76, 97
*/
for (int i = 0; i < arrLength - 1; i++) {
for (int j = arrLength - 2; j >= i; j--) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int firstIndex, int lastIndex) {
/**
* 递归条件：当开始索引小于结束索引时，否则说明两个索引重合，即只有一个数字无需再排序
*/
if (firstIndex < lastIndex) {
/**
* 维护两个指针，头指针初始位置为数组开始索引的位置，尾指针初始位置为数组结束索引的位置。
* 取待排序数组的第一个数字作为基准数。
*
* 如果头指针索引等于尾指针索引，说明只有一个数字，无需进行排序，
* 如果头指针索引小于尾指针索引，说明有多个数字待排序，开始循环。
*
* 先循环操作尾指针，如果尾指针的位置在头指针后面并且尾指针指向的数字不小于基准数，
* 就将尾指针向前移动一个位置，继续循环操作。否则说明尾指针指向的数字小于基准数或者尾指针与头指针重合，
* 此时，将尾指针指向的数字替换头指针指向的数字。
*
* 再循环操作头指针，如果尾指针的位置在头指针后面并且头指针指向的数字不大于基准数，
* 就将头指针向后移动一个位置，继续循环操作。否则说明头指针指向的数字大于基准数或者尾指针与头指针重合，
* 此时，将尾指针指向的数字替换尾指针指向的数字。
*
* 如此循环，直到头指针和尾指针重合。将基准数替换当前指针（此时，头指针和尾指针已重合）指向的数字。
*
* 49, 38, 65, 97, 76, 13 基准数：49
* ☞ ☞
* 13, 38, 65, 97, 76, 13
* ☞ ☞
* 13, 38, 65, 97, 76, 13
* ☞ ☞
* 13, 38, 65, 97, 76, 13
* ☞ ☞
* 13, 38, 65, 97, 76, 65
* ☞ ☞
* 13, 38, 65, 97, 76, 65
* ☞ ☞
* 13, 38, 65, 97, 76, 65
* ☞ ☞
* 13, 38, 65, 97, 76, 65
* ☞（指针重合）
* 13, 38, 49, 97, 76, 65
*
* 此时，一轮操作结束后，原数组被分成两段，指针所在位置（包含）前的数字都比基准数小，
* 指针所在位置（不包含）后的数字都比基准数大。
* 对两段数字继续递归操作。
*/
int lo = firstIndex;
int hi = lastIndex;
int base = arr[lo];
while (lo < hi) {
while (arr[hi] >= base && lo < hi) {
hi--;
}
arr[lo] = arr[hi];
while (arr[lo] <= base && lo < hi) {
lo++;
}
arr[hi] = arr[lo];
}
arr[hi] = base;
quickSort(arr, firstIndex, lo);
quickSort(arr, lo + 1, lastIndex);
}
}
}
直接插入排序
public class InsertSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
int arrLength = arr.length;
for (int i = 1; i < arrLength; i++) {
int currNum = arr[i];
int j;
/**
* 要插入的数字从第二个开始，此时保证要插入的数字前面的所有数字都是已经排好序的。
* 每个要插入的数字都和它之前的数字逐一比较，若前面的数字大于当前数字，
* 就把前面的数字向后挪一个位置，直到前面没有数字或者前面的某一个数字小于等于当前要插入的数字为止，
* 最后把当前要插入的数字放在对应的位置即可。
*
* 49, 38, 65, 97, 76, 13 currNum：38
* 49, 49, 65, 97, 76, 13
* 38, 49, 65, 97, 76, 13
*
* 38, 49, 65, 97, 76, 13 currNum：65
*
* 38, 49, 65, 97, 76, 13 currNum：97
*
* 38, 49, 65, 97, 76, 13 currNum：76
* 38, 49, 65, 97, 97, 13
* 38, 49, 65, 76, 97, 13
*
* 38, 49, 65, 76, 97, 13 currNum：13
* 38, 49, 65, 76, 97, 97
* 38, 49, 65, 76, 76, 97
* 38, 49, 65, 65, 76, 97
* 38, 49, 49, 65, 76, 97
* 38, 38, 49, 65, 76, 97
* 13, 38, 49, 65, 76, 97
*/
for (j = i - 1; j >= 0 && arr[j] > currNum; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = currNum;
}
}
}
希尔排序
public class ShellSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
double distance = arr.length;
int arrLength = arr.length;
/**
* 将要排序的所有数字按增量d（n/2，n为要排序数的个数）分成若干组，每组中记录的下标相差d，
* 对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。
* 当增量减到1时，最后进行一次直接插入排序即可。
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78 distance：4
* 49, 13, 65, 97, 76, 38, 27, 49, 78
* 49, 13, 27, 97, 76, 38, 65, 49, 78
* 49, 13, 27, 49, 76, 38, 65, 97, 78
*
* 49, 13, 27, 49, 76, 38, 65, 97, 78 distance：2
* 27, 13, 49, 38, 65, 49, 76, 97, 78
*
* 27, 13, 49, 38, 65, 49, 76, 97, 78 distance：1
* 13, 27, 38, 49, 49, 65, 76, 78, 97
*/
while (true) {
distance = Math.ceil(distance / 2);
int d = (int) distance;
for (int i = 0; i < d; i++) {
/**
* 进行直接插入排序操作
*/
for (int j = i + d; j < arrLength; j += d) {
int currNum = arr[j];
int k;
for (k = j - d; k >= 0 && arr[k] > currNum; k -= d) {
arr[k + d] = arr[k];
}
arr[k + d] = currNum;
}
}
if (d == 1) {
break;
}
}
}
}
简单选择排序
public class SelectSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr) {
int arrLength = arr.length;
/**
* 从第一个数字开始，从所有数字中选择一个最小的数字和第一个数字交换。
* 从第二个数字开始，从所有数字中选择一个最小的数字和第二个数字交换。
* 直到倒数第二个数和最后一个数字比较交换完成即可。
*
* 49, 38, 65, 97, 76, 13
*
* 13, 38, 65, 97, 76, 49
*
* 13, 38, 65, 97, 76, 49
*
* 13, 38, 49, 97, 76, 65
*
* 13, 38, 49, 65, 76, 97
*
* 13, 38, 49, 65, 76, 97
*/
for (int i = 0; i < arrLength - 1; i++) {
int min = arr[i];
int min_index = i;
for (int j = i + 1; j < arrLength; j++) {
if (arr[j] < min) {
min = arr[j];
min_index = j;
}
}
if (min_index != i) {
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
}
}
基数排序
public class RadixSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
/**
* 准备10个队列，序号分别为0-9。
* 先根据数组中所有数字的个位将数字放到对应的队列中，个位是几，就放到几号队列中。
* 所有数字都放入队列中后，将所有队列中的数字按照队列的序号依次取出。
* 再根据数组中所有数字的十位将数字放到对应的队列中，十位是几，就放到几号队列中。
* 所有数字都放入队列中后，将所有队列中的数字按照队列的序号依次取出。
* 再根据数组中所有数字的百位将数字放到对应的队列中，百位是几，就放到几号队列中。
* 所有数字都放入队列中后，将所有队列中的数字按照队列的序号依次取出。
* ……
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64
*
* 队列序号 0 1 2 3 4 5 6 7 8 9
* 12 13 34 65 76 97 38 49
* 64 27 78 49
*
* 12, 13, 34, 64, 65, 76, 97, 27, 38, 78, 49, 49
*
* 队列序号 0 1 2 3 4 5 6 7 8 9
* 12 27 34 49 64 76 97
* 13 38 49 65 78
*
* 12, 13, 27, 34, 38, 49, 49, 64, 65, 76, 78, 97
*/
int max = arr[0];
int arrLength = arr.length;
Queue<Integer>[] queueArr = new Queue[10];
for (int i = 0; i < arrLength; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
/**
* int maxLength = (max+"").length();
*/
int maxLength = 0;
while (max > 0) {
max /= 10;
maxLength++;
}
for (int i = 0; i < 10; i++) {
queueArr[i] = new LinkedList<>();
}
for (int i = 0; i < maxLength; i++) {
for (int j = 0; j < arr.length; j++) {
int currNum = arr[j];
int num = (int) (currNum % Math.pow(10, i + 1) / Math.pow(10, i));
queueArr[num].offer(currNum);
}
int index = 0;
for (int j = 0; j < 10; j++) {
Queue<Integer> currQueue = queueArr[j];
while (!currQueue.isEmpty()) {
arr[index] = currQueue.poll();
index++;
}
}
}
}
}
归并排序
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int lo, int hi) {
int mid = (lo + hi) / 2;
/**
* 递归条件：当开始索引小于结束索引时，否则说明两个索引重合，即只有一个数字无需再递归
*/
if (lo < hi) {
/**
* 将数组的两个子数组分别排序后，执行归并操作
*/
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
}
public static void merge(int[] arr, int lo, int mid, int hi) {
/**
* 将一个数组分成两段，可以看做是两个子数组。新建一个临时数组用于存放后续操作的数字。
* 维护两个指针，分别指向两个子数组的第一个数字。
* 比较两个指针指向的数字，将较小的一个放入临时数组，向后移动指向较小数字的指针。
* 如此循环，直到其中一个子数组中的数字都被放入临时数组，将另一个子数组中的数字也都放入到临时数组。
* 最后将临时数组中的数字放回原数组中对应的位置
*
* 49, 38, 65, 76, 13, 27, 49, 78, 97 临时数组
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
* 49, 38, 65, 97, 76, 13, 27, 49, 78
* ☞ ☞
*/
int[] tempArr = new int[hi - lo + 1];
int index = 0;
int firstCursor = lo;
int secondCursor = mid + 1;
while (firstCursor <= mid && secondCursor <= hi) {
if (arr[firstCursor] <= arr[secondCursor]) {
tempArr[index] = arr[firstCursor];
firstCursor++;
} else {
tempArr[index] = arr[secondCursor];
secondCursor++;
}
index++;
}
while (firstCursor <= mid) {
tempArr[index] = arr[firstCursor];
firstCursor++;
index++;
}
while (secondCursor <= hi) {
tempArr[index] = arr[secondCursor];
secondCursor++;
index++;
}
for (int i = 0, tempArrLength = tempArr.length; i < tempArrLength; i++) {
arr[i + lo] = tempArr[i];
}
}
}
堆排序
public class HeapSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
/**
* 从最后一个非叶子节点开始依次向前调整二叉树，直到根节点，此时，二叉树被调整为一个大顶堆。
* 最后一个叶子节点的索引为arrLength-1，则最后一个非叶子节点的索引为(arrLength-1-1)/2=arrLength/2-1。
* 调整完后的大顶堆二叉树的根节点数值（索引为0）即时最大值，将其与数组中最后一个值（索引为arrLength-1）交换，
* 固定数组最后一个值，将数组的剩余部分从根节点开始重新通过交换节点创建大顶堆。
* 调整完后的大顶堆二叉树的根节点数值（索引为0）即时最大值，将其与数组中倒数第二个值（索引为arrLength-2）交换，
* 依次循环直到数组第一个元素。
*/
int arrLength = arr.length;
int startIndex = arrLength / 2 - 1;
for (int i = startIndex; i >= 0; i--) {
transformIntoMaxHeap(arr, arrLength, i);
}
for (int i = arrLength - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
transformIntoMaxHeap(arr, i, 0);
}
}
public static void transformIntoMaxHeap(int[] arr, int arrLength, int nodeIndex) {
/**
* 对于某一个非叶子结点，如果其在数组中对应的索引为nodeIndex，并且假设它的左、右子节点存在，
* 则其左子节点的索引为nodeIndex*2+1，右子节点的索引为nodeIndex*2+2。
* 找到这三个节点中的最大值，通过交换节点位置，将最大值交换到双亲节点的位置。
* 若发生了节点交换，则最大值原来所在位置对应的大顶堆子树可能被破坏，需要递归重新调整。
*/
int leftNodeIndex = nodeIndex * 2 + 1;
int rightNodeIndex = nodeIndex * 2 + 2;
int maxValueIndex = nodeIndex;
if (leftNodeIndex < arrLength && arr[leftNodeIndex] > arr[maxValueIndex]) {
maxValueIndex = leftNodeIndex;
}
if (rightNodeIndex < arrLength && arr[rightNodeIndex] > arr[maxValueIndex]) {
maxValueIndex = rightNodeIndex;
}
if (maxValueIndex != nodeIndex) {
int temp = arr[nodeIndex];
arr[nodeIndex] = arr[maxValueIndex];
arr[maxValueIndex] = temp;
transformIntoMaxHeap(arr, arrLength, maxValueIndex);
}
}
}
计数排序
public class CountSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
/**
* 先确定数组中的最大值，建立一个临时数组，临时数组长度为最大值+1。
* 遍历数组中的所有值，将临时数组中索引等于该值的位置处的值+1。
* 循环结束后，临时数组的某个索引处的值为多少即代表原数组中该索引值的数字有多少个。
* 遍历临时数组，重新将数字依次放入原数组即可。
*
* 4, 6, 3, 1, 8, 7, 4, 2, 3 原数组
*
* 0, 0, 0, 0, 0, 0, 0, 0, 0 临时数组
* 0, 0, 0, 0, 1, 0, 0, 0, 0
* 0, 0, 0, 0, 1, 0, 1, 0, 0
* 0, 0, 0, 1, 1, 0, 1, 0, 0
* 0, 1, 0, 1, 1, 0, 1, 0, 0
* 0, 1, 0, 1, 1, 0, 1, 0, 1
* 0, 1, 0, 1, 1, 0, 1, 1, 1
* 0, 1, 0, 1, 2, 0, 1, 1, 1
* 0, 1, 1, 1, 2, 0, 1, 1, 1
* 0, 1, 1, 2, 2, 0, 1, 1, 1
*
* 1, 2, 3, 3, 4, 4, 6, 7, 8
*/
int max = arr[0];
for (int value : arr) {
max = value > max ? value : max;
}
int[] countArray = new int[max + 1];
for (int value : arr) {
countArray[value]++;
}
int index = 0;
for (int i = 0; i < max + 1; i++) {
for (int j = 0; j < countArray[i]; j++) {
arr[index] = i;
index++;
}
}
}
}
桶排序
public class BucketSort {
public static void main(String[] args) {
int[] arr =
{49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,
35, 25, 53, 51};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
/**
* 根据某个映射规则，将所有待排序的值映射到一系列的桶中，但需保证后一个桶中的值必须都大于前一个桶中的所有值。
* 例如：值除以10后，结果的整数部分是几就放入几号桶中。
* 所有数字都映射完后，对每个桶中的数字排序，可以使用JDK自带的对集合的排序。
* 最后按照桶的顺序依次将桶中的数字依次取出。
*
* 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64
*
* 桶序号
* 0
* 1 13, 12
* 2 27
* 3 38, 34
* 4 49
* 5
* 6 65, 64
* 7 76, 78
* 8
* 9 97
*
* 桶序号
* 0
* 1 12, 13
* 2 27
* 3 34, 38
* 4 49
* 5
* 6 64, 65
* 7 76, 78
* 8
* 9 97
*
* 12, 13, 27, 34, 38, 49, 64, 65, 76, 78, 97
*/
int max = arr[0];
int arrLength = arr.length;
for (int i = 0; i < arrLength; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
List<Integer>[] bucketArr = new List[max / 10 + 1];
for (int i = 0; i < max / 10 + 1; i++) {
bucketArr[i] = new LinkedList<>();
}
for (int value : arr) {
bucketArr[value / 10].add(value);
}
for (List<Integer> bucket : bucketArr) {
Collections.sort(bucket);
}
int index = 0;
for (List<Integer> bucket : bucketArr) {
for (int value : bucket) {
arr[index] = value;
index++;
}
}
}
}
