- 引言
- 排序的稳定性
- 一、直接插入排序
- 二 、希尔排序
- 三、选择排序
- 四、堆排序
- 五、冒泡排序
- 六、快速排序
- 快速排序递归写法
- 优化快速排序
- 三数取中法优化
- 快速排序的非递归写法
- 七、归并排序
- 归并排序递归写法
- 归并排序非递归写法
- 八、了解三个不需要比较数据就能进行排序的方法
- 1. 基数排序
- 2. 计数排序
- 3. 桶排序
对于一组待排序的数据，数据中有两个或两个以上的相同的元素，在经过排序后，这两个或两个以上的相同元素与之前未排序的顺序相同，则说明此排序操作是稳定的。
举例说明：
在下图中，待排序数据 ① 经过排序成为 ② ，我们发现绿色数字5和红色数字5与排序前的顺序并未发生改变，那么排序 ② 就是稳定的。
反之，排序 ③ 就是不稳定的。
思路：
从数组的第二个元素开始，遍历数组，不断地与数组第一个元素进行比较。
public class Test1 {
public static void main(String[] args) {
int[] arr = {8,5,9,4,7};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i-1;
for (; j >= 0 ; j--) {
if(arr[j] > temp){ //前面的元素比后面的元素大，就交换
arr[j+1] = arr[j];
}else {
break;
}
}
arr[j+1] = temp;
}
}
//写成这样更简洁
public static void insertSort2(int[] arr){
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i-1;
for (; j >= 0 && arr[j] > temp; j--) {
arr[j+1] = arr[j];//前面的元素比后面的元素大，就交换
}
arr[j+1] = temp;
}
}
输出结果：
希尔排序本质上就是直接插入排序，只不过对其进行了分组。当我们给定了一组数据，直接插入排序直接对这组数据进行了排序，而希尔可以将其先分成某个组别，之后对这些组别分别进行排序操作。
让我们来看下面的一个例子，可以发现每当我们进行一次排序后，小的数字都比较靠前，而大的数字都比较靠后，这就会致使下一次的排序速度的更快。
关于时间复杂度这里我还没弄懂，不过大话数据结构这本书上说明：不同的增量序列所对应的时间复杂度不同，增量序列实际上对应的就是我们进行排序时分的组别元素的个数，这和算法很有关系，我暂且不作考虑了。。。
但是有一点很重要，就是：不管我们分了多少组，每一组有多少元素，我们都必须在最后的时候，分为一组。也就是说：我们最后要对整组数据进行排序。这很好理解，因为不论我们怎么分组排序，最后很大可能都不会把一组数据排序好我们想要的结果，但是我们最后一次排序的时候一定会快很多，因为最后一组数据非常趋近于我们想要的排序序列！
public class Test2 {
public static void main(String[] args) {
int[] arr = {4,12,5,8,9,14,11,6,15,2,13,1,3,10,7};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
//希尔排序，传入 gap 进行分组
public static void shellSort(int[] arr){
int gap = arr.length;
while(gap > 1){
shell(arr, gap);
gap = gap / 2; //[7组,3组,1组]
}
shell(arr, 1);
}
//开始排序
public static void shell(int[] arr, int gap){
for (int i = gap; i < arr.length; i++) {
int temp = arr[i];
int j = i - gap;
for (; j >= 0; j = j-gap) {
if(arr[j] > temp){
arr[j+gap] = arr[j];
}else {
break;
}
}
arr[j+gap] = temp;
}
}
}
输出结果：
选择排序就是先排好第一个元素，然后排好第二个元素。。。
public class Test3 {
public static void main(String[] args) {
int[] arr = {8,5,9,4,7};
selectSort2(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
for(int j = i+1; j < arr.length; j++){
if(arr[i] > arr[j]){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
public static void selectSort2(int[] arr){
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for(int j = i+1; j < arr.length; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
if(minIndex != i){ //如果两个数相同，就不进行交换
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
}
输出结果：
堆排序在我之前的博客上有介绍，这里就不再赘述，主要阐明一下思想。
思想：
① 如果我们将待排序的一组数据进行升序，那么我们就先创建一个大顶堆，目的是始终将堆顶的元素置为最大值。
② 堆排序的实际操作就是将堆顶元素与堆尾元素进行交换。
③ 每次堆排序过后，就立即调整一次，调整为大顶堆，以便下一次排序。
public class Test4 {
public static void main(String[] args) {
//int[] arr = {8,5,9,4,7};
int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2};
createMaxHeap(arr);
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
//堆排序
public static void heapSort(int[] arr){
int end = arr.length - 1;
while (end > 0){
//1. 先交换
int temp = arr[0];
arr[0] = arr[end];
arr[end] = temp;
//2. 后调整
//每次调整的其实都是树的根节点及根节点向下
shiftDown(arr,0, end);
end--;
}
}
//创建一个大顶堆，目的是始终将堆顶的元素置为最大值
public static void createMaxHeap(int[] arr){
int child = arr.length - 1;
//处理每棵树的顺序
for (int parent = (child-1)/2; parent >= 0 ; parent--) {
shiftDown(arr,parent,arr.length);
}
}
//向下调整
public static void shiftDown(int[] arr, int parent, int len){
int child = parent*2 + 1;
while(child < len){
if(child+1 < len && arr[child] < arr[child+1]){
child++;
}
if(arr[child] > arr[parent]){
int temp = arr[parent];
arr[parent] = arr[child];
arr[child] = temp;
}
parent = child;
child = parent*2 + 1;
}
}
}
输出结果：
冒泡排序的思想就是将紧挨着的数据进行比较，一趟代表遍历完数组一次，而每一趟冒泡排序之后，最大的元素一定在最后一位。
优化分析：
在内层 for 循环中的 if 语句中，判断布尔类型 isSorted ，如果进入了 if 语句，说明进行了交换，isSorted 置为 false；反之，如果某一趟的 if 语句一次也没进去，isSorted 就为初始的 true，说明从这一趟往后，数据已经有序。
public class Test5 {
public static void main(String[] args) {
//int[] arr = {8,5,9,4,7};
int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2};
bubbleSort2(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) { //假设待排序有5个数据，只比较了4趟
for (int j = 0; j < arr.length-1-i; j++) { //每一趟比较了多少次
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
//优化
public static void bubbleSort2(int[] arr){
//举个例子 arr = {4,3,5,6,7}, 第一趟冒泡排序结束以后，实际上已经有序
for (int i = 0; i < arr.length-1; i++) {
boolean isSorted = true;
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
isSorted = false;
}
}
if(isSorted){
break;
}
}
}
}
输出结果：
思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
总结步骤：
（1）选择枢轴（基准、pivot）
（2）分割数据
① 从后面序列找比枢轴小的放到枢轴前面
② 从前面序列找枢比轴大的放到枢轴后面
通过枢轴分割数据，使得枢轴左边的值比枢轴小，枢轴右边的值比枢轴大
（3）重复递归被枢轴分割的数据，可以先处理左边的数据，再处理右边的数据
快速排序递归写法
public class Test9 {
public static void main(String[] args) {
//int[] arr = {5,2,3,9,4,7};
int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2};
int start = 0;
int end = arr.length-1;
quickSort(arr,start,end);
System.out.println(Arrays.toString(arr));
}
public static void quickSort (int[] arr, int start, int end){
if(start >= end){ //边界条件
return;
}
int i = start;
int j = end;
int temp = arr[i];
while (i < j){
//1. 从后面序列找比枢轴小的放到枢轴前面
//"="防止死循环重复赋值, i= temp){
j--;
}
arr[i] = arr[j];
//2. 从前面序列找比枢轴大的放到枢轴后面
while (i < j && arr[i] <= temp){
i++;
}
arr[j] = arr[i];
}
arr[i] = temp;
int pivot = i; //拿到每次的枢轴
//3. 分别递归求左右两边的序列
quickSort(arr,start,pivot-1);
quickSort(arr,pivot+1,end);
}
}
输出结果：
（1）随机选取基准
随机选取基准的时候，会带来不确定的因素，很有可能优化不成功。
（2）使用三数取中法来确定分割的基准，一般取左端、右端及中间的三个数，而这在这三个数种，中间大小的数被确定为基准。比方说：[ 1 3 5 ]，我们取 3，因为最小数为 1，最大数为 5。这样可以避免两种极端的情况：
① 当最大或最小的数分布在数据的两边
② 当数据整体有序的情况
（3） 将和基准相同的元素，从分散的位置聚集到一起，这样会使递归的次数减少，从而使程序运行速度更快。
（4）当分割一定的长度后，使用直接插入排序
三数取中法优化
public class Test7 {
public static void main(String[] args) {
//int[] arr = {6,1,2,7,9,3,4,5,10,8};
int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2};
//int[] arr = {5,2,3,9,4,7};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end){
if(start >= end){
return;
}
//三数取中法，防止取到顺序/逆序的情况
int midValIndex = findMidValIndex(arr, start, end);
//交换基准
int temp = arr[start];
arr[start] = arr[midValIndex];
arr[midValIndex] = temp;
int base = partition(arr,start,end); //接收基准
quickSort(arr,start,base-1);
quickSort(arr,base+1,end);
}
//找中间值
public static int findMidValIndex(int[] arr, int start, int end){
int mid = (start+end) / 2;
if(arr[start] < arr[end]){
if(arr[mid] < arr[start]){
return start;
}else if(arr[mid] > arr[end]){
return end;
}else {
return mid;
}
}else {
if(arr[mid] < arr[end]){
return end;
}else if(arr[mid] > arr[start]){
return start;
}else {
return mid;
}
}
}
//寻找基准
public static int partition(int[] arr, int start, int end){
int temp = arr[start];
while(start < end){
//在数据的后半部分寻找比基准小的
while(start < end && arr[end] >= temp){ // “=” 防止死循环，防止重复赋值
end--;
}
arr[start] = arr[end];
//在数据的前半部分寻找比基准大的
while(start < end && arr[start] <= temp){
start++;
}
arr[end] = arr[start];
}
arr[start] = temp;
return start;
}
}
快速排序的非递归写法
public class Test10 {
public static void main(String[] args) {
//int[] arr = {5,2,3,9,4,7};
int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2};
int start = 0;
int end = arr.length-1;
quickSort(arr,start,end);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end){
Stack stack = new Stack<>();
int pivot = partition(arr,start,end);
if(start+1 < pivot){
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end-1){
stack.push(pivot+1);
stack.push(end);
}
while (!stack.isEmpty()){
end = stack.pop();
start = stack.pop();
pivot = partition(arr,start,end);
if(start+1 < pivot){
stack.push(start);
stack.push(pivot-1);
}
if(pivot < end-1){
stack.push(pivot+1);
stack.push(end);
}
}
}
public static int partition (int[] arr, int i, int j){
int temp = arr[i];
while (i < j){
//1. 从后面序列找比枢轴小的放到枢轴前面
//"="防止死循环重复赋值, i= temp){
j--;
}
arr[i] = arr[j];
//2. 从前面序列找枢比轴大的放到枢轴后面
while (i < j && arr[i] <= temp){
i++;
}
arr[j] = arr[i];
}
arr[i] = temp;
return i;//拿到每次的枢轴
}
}
七、归并排序
理解归并排序之前，一定要知道两个已经有序的数组是怎么合并的，并理解它们的思想。
思想：
① 定义 s1 为 arr1 数组的初始下标，e1 为 arr1 数组的末尾下标。
② 定义 s2 为 arr2 数组的初始下标，e2 为 arr2 数组的末尾下标。
③ 将 s1 和 s2 进行比较，较小者放入新的数组中，紧着，让 s1 / s2 进行遍历，之后循环重复实现以上的操作，直到有一个数组遍历完，就可以将另一个未遍历完的数组中的剩下元素放入新数组的末尾。
代码较为简单，不再赘述。
public class Test11 {
public static void main(String[] args) {
int[] arr1 = {1,6,7,9};
int[] arr2 = {2,3,5,8};
int[] arr = merge(arr1,arr2);
System.out.println(Arrays.toString(arr));
}
public static int[] merge(int[] arr1, int[] arr2){
int[] arr = new int[arr1.length+arr2.length];
int s1 = 0;
int e1 = arr1.length-1;
int s2 = 0;
int e2 = arr2.length-1;
int i = 0;
while (s1 <= e1 && s2 <= e2){
if(arr1[s1] < arr2[s2]){
arr[i++] = arr1[s1++];
}else {
arr[i++] = arr2[s2++];
}
}
while (s1 <= e1){
arr[i++] = arr1[s1++];
}
while (s2 <= e2){
arr[i++] = arr2[s2++];
}
return arr;
}
}
现在我们来看一下归并排序的思想：
归并排序就是将在一个待排序数组中选择一个中间下标对应元素，通过这个元素分割成两个逻辑上的数组，在这两个数组中，再寻找中间对应元素，之后不断分割，直至某个数组无法再分。这样一来，就可以对某一个数组进行排序，之后再进行整合，而这里每次整合过后，都要回归原始数组中。
在下面的图片分析之中，拆就是递的过程，合就是归的过程。
public class Test12 {
public static void main(String[] args) {
//int[] arr = {9,6,7,1,3,8,5,2};
int[] arr = {8,5,9,2,6,11,26,56,35,49,99,70,21,2,4,7,2};
int low = 0;
int high = arr.length-1;
mergeSort(arr,low,high);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int low, int high){
if(low == high){
return;
}
int mid = (low+high) / 2;
mergeSort(arr,low,mid); //先拆左边
mergeSort(arr,mid+1,high); //再拆右边
merge(arr,low,mid,high); //拆完过后，开始合并
}
//合并
public static void merge(int[] arr, int low, int mid, int high){
int[] temp = new int[high-low+1];
int i = 0;
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
while (s1 <= e1 && s2 <= e2){
if(arr[s1] < arr[s2]){
temp[i++] = arr[s1++];
}else {
temp[i++] = arr[s2++];
}
}
while (s1 <= e1){
temp[i++] = arr[s1++];
}
while (s2 <= e2){
temp[i++] = arr[s2++];
}
//将 temp 中的数组拷贝至原数组中
for (int j = 0; j < i; j++) {
arr[j+low] = temp[j]; //”j+low“ 以防对原数组进行覆盖
}
}
}
输出结果：
public class Test14 {
public static void main(String[] args) {
int[] arr = {9,6,7,1,3,8,5,2};
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr){
int size = 1; // 第一次归并两个元素，第二次归并四个元素...
while (size < arr.length){
for (int i = 0; i < arr.length; i += size*2) {
int low = i;
int mid = low+size-1;
if(mid >= arr.length){
mid = arr.length-1;
}
int high = mid+size;
if(high >= arr.length){
high = arr.length-1;
}
merge(arr,low,mid,high);
}
size *= 2;
}
}
public static void merge(int[] arr, int low, int mid, int high){
int[] ret = new int[high-low+1];
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int i = 0;
while (s1 <= e1 && s2 <= e2){
if(arr[s1] < arr[s2]){
ret[i++] = arr[s1++];
}else {
ret[i++] = arr[s2++];
}
}
while (s1 <= e1){
ret[i++] = arr[s1++];
}
while (s2 <= e2){
ret[i++] = arr[s2++];
}
for (int j = 0; j < i; j++) {
arr[j+low] = ret[j];
}
}
}
输出结果：
说明：可以将下面装数据的容器想象成队列的结构，而不是栈。
