java三大排序

2019-05-12

冒泡排序

百科

冒泡排序算法的原理如下：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图示过程

动图展示

文字叙述过程

对于一组包含n个数据的记录，冒泡排序在最坏的情况下需要进行n-1趟排序

第1趟：依次比较0和1、1和2、2和3…（n-2）和（n-1）索引的元素，如果发现第1个数据大于第2个数据，交换他们，经过第1趟排序，最大的元素排到了最后

第2趟：依次比较0和1、1和2、2和3…（n-3）和（n-3）索引的元素，如果发现第1个数据大于第2个数据，交换他们，经过第2趟排序，第二大的元素排到了倒数第二个位置

…

第n-1趟：比较0和1索引的元素，如果发现第1个数据大于第2个数据，交换他们，经过第n-1趟排序，第二小的元素排到了第二个位置

代码实现

public static void bubbleSort(int arr[]) {
	System.out.println("\n由小到大排序:");
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = 0; j < arr.length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
			}
		}
	}
	for (int sorted : arr) {
		System.out.print(sorted + " ");
	}
}

代码优化

public static void bubbleSortPlus(int arr[]) {
	int temp;//临时变量，需要交换时用
	boolean flag=false;//作为优化算法，提前结束程序的标志符 
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = 0; j < arr.length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				flag=true;
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		if (!flag) { // 在一趟排序中，一次交换都没有发生过
			break;
		} else {
			flag = false; // 重置flag!!!, 进行下次判断
		}
	System.out.println("第"+(i+1)+"趟排序后结果:");
	System.out.println(Arrays.toString(arr));
	}
}

选择排序

百科

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

选择排序的思想如下
选择排序原理即是，遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。

图示过程

动图展示

文字叙述过程

这种方法的基本步骤如下：
1.先从第一个元素开始，相邻的两个元素进行比较，最后得出第一次比较中最小的元素；
2.记录好这个最小元素的位置，并把这个元素与第一个元素互换位置；
3.接着再从第二个元素开始，相邻的两个元素再进行比较，得出第二次比较中最小的元素；
4.记录好这个最小元素的位置，并把这个元素与第二个元素互换位置；
5.如此类推……最终实现有序排列。

代码实现

public static void selectSort(int arr[]) {
	System.out.println("\n由小到大排序:");
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = i + 1; j < arr.length; j++) {
			if (arr[i] > arr[j]) {
				int t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
	}
	for (int sorted : arr) {
		System.out.print(sorted + " ");
	}
}

代码实现2

public static void selectSort2(int arr[]) {
	for (int i = 0; i < arr.length - 1; i++) {
		int min = arr[i];// 定义第一个数，假设为最小的数 与第二的数去比较
		int minIndex = i;// 定义第一个数的下标，假设为最小
		// 第1轮，让第一个数与第二个数去比较
		for (int j = i + 1; j < arr.length; j++) {
			if (min > arr[j]) {// min>arr[j] 说明假定的最小值 并不是最小值
				min = arr[j];// 重置最小值
				minIndex = j;// 重置最小值索引
			}
		}
		// 将最小值放在arr[0],即交换
		arr[minIndex] = arr[i];
		arr[i] = min;
		System.out.println("第" + (i + 1) + "轮后~");
		System.out.println (Arrays.toString(arr));
	}
}

快速排序

百科

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图示过程

动图展示

文字叙述过程

这种方法的基本步骤如下：
快速排序使用分治法来把一个串（名单）分为两个子串（子列表）具体算法描述如下：
1.从数列中挑出一个元素，称为“基准”（pivot）;
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置这个称为分区（分区）操作。
3.递归地（递归）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

package cn.aparke.sort;

/**
 * 快速排序
 * @author aparke
 */
public class QuickSort {
	public static void quickSort(int[] arr, int left, int right) {

		if (left > right) {
			return;
		}

		int l = left;//  l为左索引
		int r = right;// r为右索引

		// 1.先让左边第一个数作为基准
		int pivot = arr[left]; // pivot就是基准位

		while (l < r) {

			// 1.1先看右边，依次往左递减，直到找到比pivot小的值 得到下标
			while (arr[r] >= pivot && l < r) {
				r--;
			}

			// 1.2 再看左边，依次往右递增，直到找到比pivot大的值 得到下标
			while (arr[l] <= pivot && l < r) {
				l++;// 右移
			}
			// 1.3 左边遇到比pivot大的时候和右边遇到比pivot小的时候
			// 此时如果满足条件则交换
			if (l < r) {
				int t = arr[r];
				arr[r] = arr[l];
				arr[l] = t;
			}
		}

		// 2.此时i和j的值相等 ，最后将基准位与i和j相等位置的数字交换
		// 由上面的程序可以分析处l<r 直到右移后i++后 不在进入while循环后l必定等于r 所有下面的代码可以取消if()
		if (l == r) {
			// 基准位与i和j相等位置的数字交换
			arr[left] = arr[r];
			arr[l] = pivot;
			// 3.递归调用左半数组
			quickSort(arr, left, r - 1);
			// 4.递归调用右半数组
			quickSort(arr, l + 1, right);
		}
	}

	public static void main(String[] args) {
		int[] arr = {99,56,78, 3, 4, 2, 1, 8, 7, 9, 20 };
		quickSort(arr, 0, arr.length - 1);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}

代码实现2

public static void quickSort(int arr[], int left, int right) {
	int l = left;// 左索引
	int r = right;// 右索引
	int pivot = arr[(l + r)/2];// 基准，设置为中间的数

	// 1.快速排序的第一次将比小基准的值放了在基准的左边，将比基准值大的放在了右边,在两边形成了左右子序列
	while (l < r) {
		// 在pivot的左边一直找,找到大于等于pivot值,得到下标， 退出
		while (arr[l] < pivot) {
			l += 1;
		}
		// 在基准值的右边找比基准小的值 返回下标
		while (arr[r] > pivot) {
			r -= 1;
		}
		// 由于指针有移动 所以需判断
		if (l >=r) {//找到了  
			break;
		}
		// 交换左边大的值到基准右边，右边小的值到基准左边
		int temp = arr[l];
		arr[l] = arr[r];
		arr[r] = temp;

		// 特殊情况处理 如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
		if (arr[l] == pivot) {
			r -= 1;
		}
		// 如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
		if (arr[r] == pivot) {
			l += 1;
		}
	}
	// 2.按照此方法 实现左右递归即可完成所有
	// 还需判断 如果左右指针相等的时候，有右指针前移，左指针后移
	if (l == r) {
		l+=1;
		r-=1;
	}
	 //实现左递归
	if (left < r) {
		quickSort(arr, left, r);
	}
	// 实现右递归
	if (right > l) {
		quickSort(arr, l, right);
	}

}