冒泡排序
- 基本介绍
- 冒泡排序(Bubble Sort)的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前向后移动，就像水底下的气泡一样逐渐往上冒。
- 优化：
- 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有任何交换，则说明序列有序，因此要在排序的过程中设置一个标志flag来判断元素是否进行过交换。
- 图解冒泡过程
- 一共进行数组的大小-1次的循环
- 每一趟排序的次数在逐渐的减少
- 如果我们发现在某趟排序中，没有发生依次交换，可以提前结束冒泡排序，这个就是优化
- 代码
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
// 定义一个待排序序列
// int[] numArray = {3,9,-1,10,-2};
int[] numArray = {3,9,-1,10,20};
System.out.println("排序前");
System.out.println(Arrays.toString(numArray));
bubbleSort(numArray);
System.out.println("排序后");
System.out.println(Arrays.toString(numArray));
}
public static void bubbleSort(int[] numArray) {
int temp; // 临时变量
int len = numArray.length;
boolean flag = false; // 标识变量，表示是否进行过交换
for(int i = 0; i < len - 1;i++) {
flag = false;
for(int j = 0; j < len -1 - i;j++) {
// 如果前面的数比后面的数大，则交换
if(numArray[j] > numArray[j+1]) {
flag = true;
temp = numArray[j + 1];
numArray[j + 1] = numArray[j];
numArray[j] = temp;
}
}
if(!flag) break;
}
}
}
选择排序
- 基本介绍
- 选择式排序也属于内部排序法，是从待排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
- 思想
选择排序(select sorting)也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选择最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选择最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选择最小值，与arr[2]交换，......，第i次从arr[i-1]`arr[n-1]中选取最小值，与arr[i-1]交换，......，第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 - 思路分析图
- 代码实现
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] numArray = {101,34,119,1,-1,90,123};
System.out.println("排序前");
System.out.println(Arrays.toString(numArray));
selectSort(numArray);
System.out.println("排序后");
System.out.println(Arrays.toString(numArray));
}
// 选择排序
private static void selectSort(int[] numArray) {
int len = numArray.length;
int min;
int minIndex;
for(int i = 0;i < len - 1;i++) {
min = numArray[i];
minIndex = i;
for(int j = i+1;j< len;j++) {
if(min > numArray[j]) {
// 重置
min = numArray[j];
minIndex = j;
}
}
// 将最小值放在numArr[i]，即交换
if(minIndex != i) {
numArray[minIndex] = numArray[i];
numArray[i] = min;
}
}
}
}
插入排序
- 基本介绍
- 插入式排序属于内部排序法，将待排序的第一个元素插入到前方已经排好序的序列中，从而达到排序的目的。
- 思想
插入排序(Inserting Sorting)的基本思想是：把n个待排序的元素看成是一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表 - 思路
- 代码
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
// 待排序的序列
int[] numArray = {17,3,25,14,20,9};
System.out.println("排序前");
System.out.println(Arrays.toString(numArray));
insertSort(numArray);
System.out.println("排序后");
System.out.println(Arrays.toString(numArray));
}
private static void insertSort(int[] numArray) {
int len = numArray.length;
int temp;
// 总共经过n-1轮
for(int i = 1; i < len;i++) {
temp = numArray[i];
// 从该元素的前一个元素开始比较大小
int j = i - 1;
while(j >= 0 && numArray[j] > temp) {
numArray[j + 1] = numArray[j];
j--;
}
if(j + 1 != i) {
numArray[j + 1] = temp;
}
}
}
}
希尔排序
- 简单插入排序可能存在的问题
- 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
- 希尔排序介绍
- 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
- 基本思想
- 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序：随着增量逐渐减少，每组包含的关键词越来越多。当增量减至1时，整个文件被分为1组，算法便终止。
- 示意图
- 代码
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] numArray = {8,9,1,7,2,3,5,4,6,0};
System.out.println("排序前");
System.out.println(Arrays.toString(numArray));
shellSort(numArray);
System.out.println("排序后");
System.out.println(Arrays.toString(numArray));
}
// 希尔排序
private static void shellSort(int[] numArray) {
int length = numArray.length;
int temp;
int insertIndex;
// 逐步缩小增量gap的值
for(int gap = length / 2;gap > 0; gap /= 2) {
// 从gap个元素，逐个对其所在的组进行直接插入排序
for(int i = gap;i< length;i++) {
temp = numArray[i];
insertIndex = i - gap;
while(insertIndex >= 0 && temp < numArray[insertIndex]) {
numArray[insertIndex + gap] = numArray[insertIndex];
insertIndex -= gap;
}
numArray[insertIndex + gap] = temp;
}
}
}
}
快速排序
- 快速排序(QuickSort)是对冒泡排序的一种改进。基本思想是：在待排序表L[1…n]中任选一个元素作为基准，通过一趟排序将待排序序列划分为独立的两个部分，L[1…k-1]和L[k+1…n]，使得左边的部分的所有元素小于基准，右边部分的所有数据大于等于基准。而基准数据最终放在k位置上，这个过程为一次"划分"，然后分别递归德对两个子表重复上述过程，直到每部分都只有一个元素或者为空为止，即所有元素都放在了最终的位置。
- 示意图
- 代码
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
// int[] numArray = {101,34,119,1,-1,90,123};
int[] numArray = {-9,-567,0,24,77,70};
System.out.println("排序前");
System.out.println(Arrays.toString(numArray));
quickSort(numArray,0,numArray.length-1);
System.out.println("排序后");
System.out.println(Arrays.toString(numArray));
}
private static void quickSort(int[] numArray,int low,int high) {
// 如果还剩一个元素或者没有元素，就结束
if(low >= high) return;
// 将最后一个元素作为基准，你可以任意选择
int pivot = numArray[high];
int mid = high;
int i = low;
int j = high;
while(low < high) {
// 找到第一个比基准大的数
while(low < high && numArray[low] <= pivot) {
low++;
}
numArray[high] = numArray[low];
// 找到第一个比基准小的数
while(high > low && numArray[high] >= pivot) {
high--;
}
numArray[low] = numArray[high];
}
// 最后基准元素要放的位置
numArray[low] = pivot;
mid = low;
// 递归左边的
quickSort(numArray,i,mid - 1);
quickSort(numArray,mid + 1,j);
}
}
归并排序
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)
思想
示意图：
- 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并成最终序列[1,2,3,4,5,6,7,8]，实现步骤如下
- 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并成最终序列[1,2,3,4,5,6,7,8]，实现步骤如下
代码
- 给你一个数组，arr = Array(8,4,5,7,1,3,6,2)，请使用归并排序完成排序
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { System.out.println("排序前"); int[] array = {8,4,5,7,1,3,6,2}; System.out.println(Arrays.toString(array)); MergeSort(array,0,array.length-1); System.out.println("排序后"); System.out.println(Arrays.toString(array)); } public static void MergeSort(int[] arr,int low,int high) { if(low < high) { int mid = (low + high) / 2; // 递归左边的序列 MergeSort(arr,low,mid); // 递归右边的 MergeSort(arr,mid + 1,high); // 合并 Merge(arr,low,mid,high); } } /** * 合并 * @param arr 待排序的数组 * @param low 左边起始下标 * @param mid 左边最后一个元素下标 * @param high 最后一个下标 */ private static void Merge(int[] arr, int low, int mid, int high) { // 创建一个辅助数组 int[] temp = new int[arr.length]; // 将原数组待排序的序列拷贝一份到辅助数组 for(int i = low;i <= high;i++) { temp[i] = arr[i]; } int i,j,k; for(i=low,j=mid+1,k=low;i<=mid&&j<=high;k++){ if(temp[i] <= temp[j]) { arr[k] = temp[i++]; }else { arr[k] = temp[j++]; } } while(i <= mid) arr[k++] = temp[i++]; while(j <= high) arr[k++] = temp[j++]; } }
基数排序
- 介绍
- 基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
- 基数排序属于稳定性的排序，基数排序法是效率高的稳定性排序法。
- 基数排序(Radix Sort)是桶排序的扩展。
- 基数排序是1887年赫尔曼 何乐礼发明的，它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
- 基本思想
- 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
- 图文说明
- 代码实现
- 要求：将数组[53,3,542,748,14,214]使用基数排序，进行升序排序
import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arr = {53,3,542,748,14,214}; System.out.println("排序前"); System.out.println(Arrays.toString(arr)); radixSort(arr); System.out.println("排序后"); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr) { // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组 // 为了防止数据溢出，每个一位数组(桶)，大小定为arr.length int[][] bucket = new int[10][arr.length]; // 为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数 int[] bucketCount = new int[10]; // 找出最大位数 int max = arr[0]; for(int i = 1; i < arr.length; i++) { if(arr[i] > max) { max = arr[i]; } } // 得到数组中最大的数是几位数 int maxLength = (max + "").length(); for(int i = 1,n=1; i <= maxLength;i++,n*=10) { // 将所有元素放在桶中 for(int j = 0; j < arr.length; j++) { int digit = arr[j] / n % 10; bucket[digit][bucketCount[digit]] = arr[j]; bucketCount[digit]++; } int index = 0; // 收集所有元素 for(int k = 0; k < bucket.length; k++) { for(int l = 0; l < bucketCount[k]; l++) { arr[index++] = bucket[k][l]; } // 每一次循环结束，都需要将count清零 bucketCount[k] = 0; } } } }- 说明
- 基数排序是对传统桶排序的扩展，速度很快。
- 基数排序是经典的空间换时间，占用内存很大，当对海量数据排序时，容易造成OutOfMemeryError
- 基数排序时稳定的
- 有负数的数组，我们不能用基数来进行排序
- 常用算法对比
