本文共 11990 字，大约阅读时间需要 39 分钟。
声明: 该文内部分图片转自某站相关课程ppt的截图, 如有侵权私信删除, 谢谢!
1 快速排序
基本思想:
- 选定Pivot中心轴
- 将大于Pivot的数字放在Pivot的右边
- 将小于Pivot的数字放在Pivot的左边
- 分别对左右子序列重复前三步操作
代码:
//快速排序public class QuickSort { @Test public static void main(String[] args) { int[] array = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; quickSort(array); System.out.println(Arrays.toString(array)); } public static void quickSort(int[] array) { int len; if(array == null || (len = array.length) == 0 || len == 1) { return ; } sort(array, 0, len - 1); } /** * 快排核心算法，递归实现 * @param array * @param left * @param right */ public static void sort(int[] array, int left, int right) { if(left > right) { return; } // base中存放基准数 int base = array[left]; int i = left, j = right; while(i != j) { // 顺序很重要，先从右边开始往左找，直到找到比base值小的数 while(array[j] >= base && i < j) { j--; } // 再从左往右边找，直到找到比base值大的数 while(array[i] <= base && i < j) { i++; } // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置 if(i < j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } // 将基准数放到中间的位置（基准数归位） array[left] = array[i]; array[i] = base; // 递归，继续向基准的左右两边执行和上面同样的操作 // i的索引处为上面已确定好的基准值的位置，无需再处理 sort(array, left, i - 1); sort(array, i + 1, right); }} 2 插入排序
基本思想: 在要排序的一组数中，假设前面(n-1)[n>=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环直到全部排好顺序
代码:
public class insertSort { //插入排序 @Test public static void main(String[] args) { int a[] = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; int temp = 0; for (int i = 0; i < a.length; i++) { int j = i - 1; temp = a[i]; for (; j >= 0 && temp < a[j]; j--) { a[j + 1] = a[j]; } a[j+1]=temp; } for (int i = 0; i < a.length; i++) { String str = a[i]+","; System.out.println(str); } }} 3 选择排序
时间复杂度
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
首先我们来了解一下选择排序。选择排序是一种简单、直观的排序方法。
它的核心思想是: 每次从待排序的数字中找出最小值，将最小值放在待排序数字的最前面，这样就确定了一个数字的位置。接着，再从剩下的未排序的数字中再找出一个最小值出来，放在剩下数字的前面，这样就确定了第二个数字的位置。以次类推,n个数字只要重复n-1趟，我们就可以将这n个数字按从小到大的顺序排好。如果像按从大到小的顺序排好，可以每次找出最大值。
代码:
public class selectSort { //选择排序 @Test public static void main(String[] args) { int arr[] = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; for (int i = 0; i < arr.length; i++) { //最小数的索引 int minIndex = i; for (int j = i; j < arr.length; j++) { //找到最小数，并记录最小数的索引 if (arr[j] < arr[minIndex]) { minIndex = j; } } //交换符合条件的数 int tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } System.out.println(Arrays.toString(arr)); }} 4 冒泡排序
基本概念: 依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟:首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟:仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数)，将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的)，第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数)。如此下去，重复以上过程，直至最终完成排序。
实现思路: 用二重循环实现，外循环变量设为i，内循环变量设为j。假如有n个数需要进行排序，则外循环重复n-1次，内循环依次重复n-1，n-2, …, 1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2…n-1，对于每一个i，j的值依次为0,1,2,…n-i。设数组长度为N:
-
比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
-
这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位。
-
N=N-1, 如果N不为0就重复前面二步，否则排序完成。
代码:
public class bubbleSort { //冒泡排序 @Test public static void main(String[] args) { int a[] = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; int temp; //临时变量 for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - 1; j++) { if (a[j + 1] < a[j]) { temp = a[j + 1]; a[j + 1] = a[j]; a[j] = temp; } } } System.out.println(Arrays.toString(a)); }} 5 鸡尾酒排序
1.概念:
鸡尾酒排序也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
2.原理:
使用鸡尾酒排序为一列数字进行排序的过程.
数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
代码:
public class CocktailSort { //鸡尾酒排序 @Test public static void main(String[] args) { int[] array = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; for (int i = 0; i < array.length / 2; i++) { for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } for (int j = array.length - i - 1; j > i; j--) { if (array[j] < array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } System.out.println(Arrays.toString(array)); }} 6 归并排序
概念: 归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
思路:
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作 第三, 合并: 合并两个排好序的子序列,生成排序结果.
算法实现:
此算法的实现不像图示那样简单，现分三步来讨论
-
首先从宏观上分析，首先让子表表长 L=1 进行处理；不断地使 L=2*L ，进行子表处理，直到 L>=n 为止，把这一过程写成一个主体框架函数 mergesort 。
-
然后对于某确定的子表表长 L ，将 n 个记录分成若干组子表，两两归并，这里显然要循环若干次，把这一步写成一个函数 mergepass ，可由 mergesort 调用。最后再看每一组（一对）子表的归并，其原理是相同的，只是子表表长不同，换句话说，是子表的首记录号与尾记录号不同，把这个归并操作作为核心算法写成函数 merge ，由 mergepass 来调用。假设我们有一个没有排好序的序列，那么首先我们使用分割的办法将这个序列分割成一个一个已经排好序的子序列
-
然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。
代码:
public class MergeSort { // 归并排序 @Test public static void main(String[] args) { int a[] = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; sort(a, 0, a.length - 1); System.out.println(Arrays.toString(a)); } public static int[] sort(int[] a, int low, int high) { int mid = (low + high) / 2; if (low < high) { sort(a, low, mid); sort(a, mid + 1, high); //左右归并 merge(a, low, mid, high); } return a; } public static void merge(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low; int j = mid + 1; int k = 0; // 把较小的数先移到新数组中 while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 把左边剩余的数移入数组 while (i <= mid) { temp[k++] = a[i++]; } // 把右边边剩余的数移入数组 while (j <= high) { temp[k++] = a[j++]; } // 把新数组中的数覆盖nums数组 for (int x = 0; x < temp.length; x++) { a[x + low] = temp[x]; } }} 7 基数排序(桶排序)
基数排序(radix sort)又称桶排序（bucket sort），相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。我在上一篇讲到的计数排序也属于这种排序模式，上一篇结尾处提到了计数排序的稳定性，即排序前和排序后相同的数字相对位置保持不变。今天我们要说的基数排序就要利用到排序稳定性这一点。
// 基数排序(radix sort)又称桶排序（bucket sort）public class BucketSort { @Test public static void main(String[] args) { int array[] = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; // 桶 10个桶 每个桶的最大容量默认为数组长度 int[][] bucket = new int[10][array.length]; // 每个桶的当前容量 int[] capacity = new int[10]; //元素求出最大数 int max = array[0]; for (int r = 0; r < array.length; r++) { if (array[r] > max) { max = array[r]; } } //求出最大长度 用于判断循环几大轮 int length = (max + "").length(); //取得（个位 十位 百位。。。。）基数 for (int b = 0, u = 1; b < length; b++, u *= 10) { for (int i = 0; i < array.length; i++) { int base = array[i] / u % 10; //比如基数为 4 //将基数按照规则放进桶中 bucket[base][capacity[base]] = array[i]; //放进第四个桶中 的第一几个当前容量位置 capacity[base]++; //容量增加 } // 取出数据 int d = 0; for (int k = 0; k < capacity.length; k++) { if (capacity[k] != 0) { for (int p = 0; p < capacity[k]; p++) { array[d] = bucket[k][p]; d++; } } //注意：清零 capacity[k] = 0; } } System.out.println(Arrays.toString(array)); }} 8 希尔排序
基本思想:
- 算法先将要排序的一组数按某个增量d (n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d
- 对每组中全部元素进行直接插入排序，然后再用一个较小的增量(d/2)对它进行分组，在每组中再进行直接插入排序。
- 当增量减到1时，进行直接插入排序后，排序完成。
例子: 此处以人的身高为数值大小进行对比, 同色的人为同组:
知识点:
希尔排序最后一组是用的插入算法, 那么为什么不一开始就用插入排序?
下图为比较一个长度为10000的数组两种算法情况下所需要比较的次数.
// 希尔排序public class ShellsSort { @Test public static void main(String[] args) { int arr[] = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; shellSort(arr); System.out.println(Arrays.toString(arr)); } private static void shellSort(int[] arr) { //step:步长 for (int step = arr.length / 2; step > 0; step /= 2) { //对一个步长区间进行比较 [step,arr.length) for (int i = step; i < arr.length; i++) { int value = arr[i]; int j; //对步长区间中具体的元素进行比较 for (j = i - step; j >= 0 && arr[j] > value; j -= step) { //j为左区间的取值，j+step为右区间与左区间的对应值。 arr[j + step] = arr[j]; } //此时step为一个负数，[j + step]为左区间上的初始交换值 arr[j + step] = value; } } }} 9 堆排序
概念: 堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
什么是堆?
堆是一个树形结构，其实堆的底层是一棵完全二叉树。而完全二叉树是一层一层按照进入的顺序排成的。按照这个特性，我们可以用数组来按照完全二叉树实现堆。
两种方法:
- 大顶堆:每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。
- 小顶堆:每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。
- 堆排序的平均时间复杂度为O(nlogn)
推排序思想:
- 构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
- 将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。
- 重新构建堆。重复2~3，直到待排序列中只剩下一个元素(堆顶元素)。
代码:
// 堆排序public class HeapSort { @Test public static void main(String[] args) { int[] arr = { 52, 15, 87, 98, 22, 41, 21, 32, 14, 22, 9}; heapSort(arr); System.out.println(Arrays.toString(arr)); } /** * 创建堆， * @param arr 待排序列 */ private static void heapSort(int[] arr) { //创建堆 for (int i = (arr.length - 1) / 2; i >= 0; i--) { //从第一个非叶子结点从下至上，从右至左调整结构 adjustHeap(arr, i, arr.length); } //调整堆结构+交换堆顶元素与末尾元素 for (int i = arr.length - 1; i > 0; i--) { //将堆顶元素与末尾元素进行交换 int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //重新对堆进行调整 adjustHeap(arr, 0, i); } } /** * 调整堆 * @param arr 待排序列 * @param parent 父节点 * @param length 待排序列尾元素索引 */ private static void adjustHeap(int[] arr, int parent, int length) { //将temp作为父节点 int temp = arr[parent]; //左孩子 int lChild = 2 * parent + 1; while (lChild < length) { //右孩子 int rChild = lChild + 1; // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (rChild < length && arr[lChild] < arr[rChild]) { lChild++; } // 如果父结点的值已经大于孩子结点的值，则直接结束 if (temp >= arr[lChild]) { break; } // 把孩子结点的值赋给父结点 arr[parent] = arr[lChild]; //选取孩子结点的左孩子结点,继续向下筛选 parent = lChild; lChild = 2 * lChild + 1; } arr[parent] = temp; }} 转载地址：https://blog.csdn.net/weixin_40597409/article/details/113793899 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
