博客

Java排序方法大全

  • Post author:
  • Post category:java




前言



关于稳定排序和不稳定排序

通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

问题来了，什么时候必须要求使用稳定排序呢？

由上面的定义可知道稳定性排序保证了排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

那么，当现实应用中排序的需求需要区别先后顺序的时候就必须用到稳定排序。


不稳定的排序：选择排序、快速排序、希尔排序、堆排序

稳定排序：冒泡排序、插入排序、归并排序



排序概述

以下所述排序方法的基本思路和代码针对于将数据序列以从小到大的顺序排列，逆序排列基本思路和代码类似，当然除了以下七种排序方法外，还有很多，这里不再赘述，请大家自行学习。

文中相关排序方式视频及代码详见：

排序视频及代码



提取码：0w7a

先将交换数组中两个元素的值抽取成公共方法，代码如下： 

/*
 * 交换数组中的两个元素
 */
public static void swap(int[] data, int i, int j) {
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}



1. 冒泡排序法



1.1 基本思路

冒泡排序，顾名思义就是像泡泡一样，大的泡泡就冒的快，排在最上面，最容易冒出水面。我们运用这个思路，对序列进行排序，排序步骤如下：

  • 依次比较相邻的两个数，将小数放在前面，大数放在后面。

    *第一趟比较：首先比较第1个和第2个数，将小数放前，大数放后。 然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
  • 至此第一趟结束，将最大的数放到了最后。
  • 第二趟比较：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的）。
  • 第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
  • 如此下去，重复以上过程，直至最终完成排序。

    在这里插入图片描述



1.2 代码实现

public static void sort(int[] data) {
   	for (int i = 0; i < data.length - 1; i++) {
   		for (int j = 0; j < data.length - 1 - i; j++) {
   			if (data[j] > data[j + 1]) {
   				swap(data, j, j + 1);
   			}
   		}
   	}
   }



2. 选择排序法



2.1 基本思路

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

在这里插入图片描述



2.2 代码实现

public class SelectionSort {
	public static void sort(int[] data) {
		for (int x = 0; x < data.length - 1; x++) {
			for (int y = x + 1; y < data.length; y++) {
				if (data[y] < data[x]) {
					swap(data, x, y);
				}
			}
		}
	}
}



3. 插入排序法



3.1 基本思路

将n个元素的数列分为已有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

在这里插入图片描述



3.2 代码实现

public static void sort(int[] data) {
		for (int i = 1; i < data.length; i++) {
			for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
				swap(data, j, j - 1);
			}
		}
	}



4. 归并排序法



4.1 基本思路

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

在这里插入图片描述 

public static void sort(int[] data) {
	int[] temp = new int[data.length];
	mergeSort(data, temp, 0, data.length - 1);
}

private static void mergeSort(int[] data, int[] temp, int l, int r) {
	int mid = (l + r) / 2;
	if (l == r)
		return;
	mergeSort(data, temp, l, mid);
	mergeSort(data, temp, mid + 1, r);

	for (int i = l; i <= r; i++) {
		temp[i] = data[i];
	}
	int i1 = l;
	int i2 = mid + 1;
	for (int cur = l; cur <= r; cur++) {
		if (i1 == mid + 1)
			data[cur] = temp[i2++];
		else if (i2 > r)
			data[cur] = temp[i1++];
		else if (temp[i1] < temp[i2])
			data[cur] = temp[i1++];
		else
			data[cur] = temp[i2++];
	}
}



5. 快速排序法



5.1 基本思路

快速排序法通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

在这里插入图片描述



5.2 代码实现

public static void sort(int[] data) {
	quickSort(data, 0, data.length - 1);
}

private static void quickSort(int[] data, int i, int j) {
	int pivotIndex = (i + j) / 2;
	// swap
	swap(data, pivotIndex, j);

	int k = partition(data, i - 1, j, data[j]);
	SortTest.swap(data, k, j);
	if ((k - i) > 1)
		quickSort(data, i, k - 1);
	if ((j - k) > 1)
		quickSort(data, k + 1, j);
}

private static int partition(int[] data, int l, int r, int pivot) {
	do {
		while (data[++l] < pivot);
		while ((r != 0) && data[--r] > pivot);
		swap(data, l, r);
	} while (l < r);
	swap(data, l, r);
	return l;
}



6. 希尔排序法



6.1 基本思路

希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的法。在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

在这里插入图片描述



6.2 代码实现

public static void sort(int[] data) {
for (int i = data.length / 2; i > 2; i /= 2) {
		for (int j = 0; j < i; j++) {
			insertSort(data, j, i);
		}
	}
	insertSort(data, 0, 1);
}

private static void insertSort(int[] data, int start, int inc) {
	for (int i = start + inc; i < data.length; i += inc) {
		for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
			swap(data, j, j - inc);
		}
	}
}



7. 堆排序



7.1 基本思路


预备知识


堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

**堆：堆是具有以下性质的完全二叉树，每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。**如下图：

在这里插入图片描述

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

在这里插入图片描述

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：


大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

在这里插入图片描述



7.2 代码实现

public static void sort(int[] data) {
MaxHeap h = new MaxHeap();
	h.init(data);
	for (int i = 0; i < data.length; i++)
		h.remove();
	System.arraycopy(h.queue, 1, data, 0, data.length);
}

private static class MaxHeap {

	void init(int[] data) {
		this.queue = new int[data.length + 1];
		for (int i = 0; i < data.length; i++) {
			queue[++size] = data[i];
			fixUp(size);
		}
	}

	private int size = 0;

	private int[] queue;

	public int get() {
		return queue[1];

	}

	public void remove() {
		swap(queue, 1, size--);
		fixDown(1);
	}

	// fixdown
	private void fixDown(int k) {
		int j;
		while ((j = k << 1) <= size) {
			if (j < size && queue[j] < queue[j + 1])
				j++;
			if (queue[k] > queue[j]) // 不用交换

				break;
			swap(queue, j, k);
			k = j;
		}
	}

	private void fixUp(int k) {
		while (k > 1) {
			int j = k >> 1;
			if (queue[j] > queue[k])
				break;
			swap(queue, j, k);

			k = j;
		}
	}
}


版权声明：本文为qq_41609775原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
Tags: