排序算法的思维分析以及java实现

排序算法的思想分析以及java实现

毫无疑问，排序在数据结构中的地位是相当的重要的。

（强烈推荐的常用算法类学习文章：白话经典算法）
（学习期间参考了文章：点击打开链接）

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。

具体细分的话大概如下：

基于关键词比较的排序算法有插入排序（直接插入排序及Shell排序）、交换排序（冒泡排序及快速排序）、选择排序（直接选择和堆排序）、合并排序等。
按时间代价分类：平方阶排序算法，它们一般都比较简单，特点是容易实现，但时间复杂度相对较高，最坏情况下时间复杂度一般为O(n2)；线性对数阶算法，以分治策略算法为主，最坏情况下时间复杂度一般为O(nlogn).
分布排序算法不以关键词比较为基础，有较低的时间代价(即O(n))，但是需要对数据集有一定先验知识，比如数据分布于哪个区间内等。

一.插入排序

直接插入排序（InsertSort)
（直接）插入排序，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入,该位置之后的序列依次向后移动一个单位
(很经典的一个类比就是摸扑克牌：在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。)

平均复杂度为O(n^2)

代码实现：
<span style="font-size:14px;">public class InsertSort {
	public static void main(String[] args) {
		int[] A={2,3,7,1,5,6,4};
		System.out.println("排序之前的数组A：");
		for(int i=0;i<A.length;i++)
			System.out.print(A[i]+" ");
		
		//直接插入排序
		for(int i=1;i<A.length;i++){
			int temp=A[i];	//待插入的元素
			int j;
			for(j=i-1;j>=0;j--){	
				if(A[j]>temp){
					A[j+1]=A[j];	//将大于temp的元素向后移动一位
				}
				else
					break;
			}
			A[j+1]=temp;
		}
		
		System.out.println("\n\n排序之后的数组Ａ");
		for(int i=0;i<A.length;i++)
			System.out.print(A[i]+" ");
	}

}</span>
运行结果：
Shell（希尔）排序(ShellSort)

基本思想：该方法实质上是一种渐减增量排序。它是直接插入排序算法的一种更高效的改进版本，是不稳定的一种排序算法。
把记录按下标的一定增量分组，对每组使用直接插入排序法，随着增量逐渐减少，所分成的组包含的关键词越来越多，到增量值减至1时，整个文件恰好被分成一个组，算法便告终止。

平均复杂度为O(nLogn)，是不稳定的排序方法

代码实现：
public class ShellSort {
	public static void main(String[] args) {
		int[] A = { 3, 2, 7, 1, 5, 6, 4 };
		System.out.println("排序之前的数组A：");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");

		// 希尔排序
		int gap = A.length / 2;
		while (1 <= gap) {
			// 把距离为 gap 的元素编为一个组，扫描所有组
			for (int i = gap; i < A.length; i++) {
				int j = 0;
				int temp = A[i];
				// 对距离为 gap 的元素组进行排序
				for (j = i - gap; j >= 0 && temp < A[j]; j = j - gap) {
					A[j + gap] = A[j];
				}
				A[j + gap] = temp;
			}
			gap = gap / 2; // 减小增量
		}

		System.out.println("\n\n排序之后的数组Ａ");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");
	}

}
二分插入排序(BinInsertSort) 也叫对半插入排序

基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。

平均复杂度为：O(n^2)，二分插入是一个稳定的排序方法
代码实现：
public class BinInsertSort {
	public static void main(String[] args) {
		int[] A = { 3, 2, 7, 1, 8, 5, 6, 4 };
		System.out.println("排序之前的数组A：");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");

		// 二分插入排序
		for (int i = 0; i < A.length; i++) {
			int temp = A[i];	//待插入的元素
			int left = 0;
			int right = i - 1;
			int mid = 0;
			while (left <= right) {
				mid = (left + right) / 2;
				if (temp < A[mid]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			}
			for (int j = i - 1; j >= left; j--) {
				A[j + 1] = A[j];	//将大于temp的元素向后移动一位
			}
			if (left != i) {
				A[left] = temp;
			}
		}

		System.out.println("\n\n排序之后的数组Ａ");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");
	}
}
插入排序小结：

以上三种排序方法的核心都是插入排序，直接插入排序对于大部分有序的序列排序时速度快；希尔排序则利用直接插入排序对于大部分有序的序列速度快的特点，先让大部分序列有序，以此来提高排序效率；二分插入排序在直接插入的基本上改变了查找元素插入位置的方法，对于完全无序的序列来说，速度会变快，但是对开大部分有序的序列反而会更慢。

二.交换排序

冒泡排序（BubbleSort）

基本思想：自下而上（或从左到右）比较相邻记录的关键词，交换存在逆序的记录；使关键词较大的记录如气泡一般逐渐往上“飘移”直至“水面”（序列顶端）。
（这是原始的冒泡排序，还有一种加强版的冒泡排序，具体操作是在较大的元素向上“浮”的过程中较小的元素同时向下“沉”，这样能加速排序的过程。）

排序算法的思维分析以及java实现

平均复杂度为：O(n^2)，它是一个稳定的排序算法

代码实现：

public class BubbleSort {
	public static void main(String[] args) {
		int[] A = { 3, 2, 7, 1, 8, 5, 6, 4 };
		System.out.println("排序之前的数组A：");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");

		// 冒泡排序
		for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < A.length - i - 1; j++) {
				if (A[j] > A[j + 1]) {
					int temp = A[j];
					A[j] = A[j + 1];
					A[j + 1] = temp;
				}
			}

		}
		System.out.println("\n\n排序之后的数组Ａ");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");
	}
}

快速排序（QuickSort）也叫分划交换排序

思想：（解释非常好的一篇文章：点击打开链接）

不断交换反序对。任取待排序文件中的某个记录(例如取第一个记录)作为基准，按照该记录的关键词大小，将整个文件划分为左右两个子文件。
左侧子文件中所有记录的关键词都小于或等于基准记录的关键词；
右侧子文件中所有记录的关键词都大于或等于基准记录的关键词。

排序算法的思维分析以及java实现

平均复杂度为O(nLogn),是不稳定的排序方法。

代码实现：

public class QuickSort {

	public static void quickSort(int[] A, int right, int left) {
		int i, j, t, temp;
		if (left < right)
			return;

		temp = A[right]; // temp中存的就是基准数
		i = right;
		j = left;
		while (i != j) {
			// 顺序很重要，要先从右边开始找
			while (A[j] >= temp && i < j)
				j--;
			// 再找左边的
			while (A[i] <= temp && i < j)
				i++;
			// 交换两个数在数组中的位置
			if (i < j) {
				t = A[i];
				A[i] = A[j];
				A[j] = t;
			}
		}
		// 最终将基准数归位
		A[right] = A[i];
		A[i] = temp;

		quickSort(A, right, i - 1);// 继续处理左边的，这里是一个递归的过程
		quickSort(A, i + 1, left);// 继续处理右边的 ，这里是一个递归的过程
	}

	public static void main(String[] args) {
		int[] A = { 3, 2, 7, 1, 8, 5, 6, 4 };
		System.out.println("排序之前的数组A：");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");

		// 快速排序
		quickSort(A, 0, A.length - 1);

		System.out.println("\n\n排序之后的数组Ａ");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");
	}
}

交换排序小结：
其本质的思想是不变的：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

应用交换排序基本思想的主要排序方法有即是冒泡排序（Bubble sort）和快速排序（Quick sort）。
　冒泡是一种很基础的排序方法，但是其效率低，而快速排序效率比较高，是使用的比较多的排序方法。　　

三.选择排序

直接选择排序(SelectSort)
思想：对待排序的文件进行n次选择，其中第 i 次选择第 i 小（大）的记录放在第 i（n-i+1）个位置上。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始(最后)位置，直接选择排序然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾（前面）。
以此类推，直到所有元素均排序完毕。

排序算法的思维分析以及java实现

平均复杂度为O(n^2),是一种不稳定的排序方法。

代码实现：

public class SelectSort {

	public static void selectSort(int[] a) {

		for (int i = 0; i < a.length; i++) {
			for (int j = i + 1; j < a.length; j++) {
				if (a[i] > a[j]) {
					swap(a, i, j);
				}
			}
		}
	}

	public static void swap(int[] a, int b, int c) {
		if (b == c)
			return;
		a[b] = a[b] ^ a[c];
		a[c] = a[b] ^ a[c];
		a[b] = a[b] ^ a[c];
	}

	public static void main(String[] args) {
		int[] A = { 3, 2, 7, 1, 8, 5, 6, 4 };
		System.out.println("排序之前的数组A：");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");

		// 直接选择排序
		selectSort(A);

		System.out.println("\n\n排序之后的数组Ａ");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");
	}
}

堆排序(HeapSort)
思想：首先要了解堆这种数据结构以及如何建堆（堆大致可以理解为一颗完全二叉树），堆分为大根堆（父节点的数据大于等于子节点）和小根堆（父节点的数据小于等于子节点），想要最终得到非降序列，堆排序一般使用大根堆。
具体可以参考文章点击打开链接，写的特别详细。

堆排序算法的粗略描述如下：

（l）建立包含K1，K2，…，Kn的堆；

（2）FORi＝nTO 2 STEP –1 DO

（R1«Ri ．

重建包含K1，K2，…，Ki–1的堆）

堆排序的平均复杂度为：O(nlogn),是一种不稳定的排序方法

代码实现：

import java.util.Arrays;

public class HeapSort {

	public static void heapSort(int[] a) {
		int arrayLength = a.length;
		// 循环建堆
		for (int i = 0; i < arrayLength - 1; i++) {
			// 建堆
			buildMaxHeap(a, arrayLength - 1 - i);
			// 交换堆顶和最后一个元素
			swap(a, 0, arrayLength - 1 - i);
			//System.out.println("\n"+Arrays.toString(a));
		}
	}

	// 对data数组从0到lastIndex建大顶堆
	public static void buildMaxHeap(int[] data, int lastIndex) {
		// 从lastIndex处节点（最后一个节点）的父节点开始
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			// k保存正在判断的节点
			int k = i;
			// 如果当前k节点的子节点存在
			while (k * 2 + 1 <= lastIndex) {
				// k节点的左子节点的索引
				int biggerIndex = 2 * k + 1;
				// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
				if (biggerIndex < lastIndex) {
					// 若果右子节点的值较大
					if (data[biggerIndex] < data[biggerIndex + 1]) {
						// biggerIndex总是记录较大子节点的索引
						biggerIndex++;
					}
				}
				// 如果k节点的值小于其较大的子节点的值
				if (data[k] < data[biggerIndex]) {
					// 交换他们
					swap(data, k, biggerIndex);
					// 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
					k = biggerIndex;
				} else {
					break;
				}
			}
		}
	}

	// 交换
	private static void swap(int[] data, int i, int j) {
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}

	public static void main(String[] args) {
		int[] A = { 3, 2, 7, 1, 8, 5, 6, 4 };
		System.out.println("排序之前的数组A：");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");

		// 堆排序
		heapSort(A);

		System.out.println("\n\n排序之后的数组Ａ");
		for (int i = 0; i < A.length; i++)
			System.out.print(A[i] + " ");
	}

}

选择排序小结：
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
　　堆排序可通过树形结构保存部分比较结果，可减少比较次数。复杂度低，实用性更强。

四.合并排序

d 合并排序：

排序算法的思维分析以及java实现

相关推荐