「数据结构与算法」基础排序算法

「数据结构与算法」基础排序 【「数据结构与算法」基础排序】交换排序：

快速排序
冒泡排序

交换排序快速排序
思路：
在数组中找一个元素(节点)，比它小的放在节点的左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。
不断执行这个操作...
实现：

public static void quickSort(int[] array, int l, int r) { int leftPos = l; int rightPos = r; // 支点 // 该值可以选任意值 int pivot = array[(l + r) / 2]; // 支点左边的值全部小于支点 // 支点右边的值全部大于支点 while (leftPos <= rightPos) { // 从左开始，寻找比支点大的位置 while (array[leftPos] < pivot) { leftPos++; }// 从右开始，寻找比支点小的位置 while (array[rightPos] > pivot) { rightPos--; }if (leftPos <= rightPos) { // 交换左右数值 int temp = array[leftPos]; array[leftPos] = array[rightPos]; array[rightPos] = temp; leftPos++; rightPos--; } }if (rightPos > l) { quickSort(array, l, rightPos); }if (leftPos < r) { quickSort(array, leftPos, r); } }

冒泡排序
思路：
俩俩交换，大的放在后面，第一次排序后最大值已在数组末尾
因为俩俩交换，需要 n-1 趟排序，比如10个数，需要9趟排序
实现：

public static void popupSort(int[] array) { // 每一轮把最大的值像冒泡泡一样冒到最后一位 for (int i = 0; i < array.length - 1; i++) { // 判断是否修改 boolean isChange = false; for (int j = 0; j < array.length - 1 - i; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; isChange = true; } }// 若无修改代表数组已经有序 if (isChange == false) { break; } } }