# Java排序方法

**Repository Path**: lu-penghui/java-sorting-method

## Basic Information

- **Project Name**: Java排序方法
- **Description**: 用来记录，排序的代码实现以及原理
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-05-06
- **Last Updated**: 2022-05-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Sort

## README

# 此仓库用来记录总结的java排序方法
### 所有排序分类图
![输入图片说明](img/sort.jpg)
### 一、交换排序
交换排序，就是俩个元素之间进行比较交换，根据交换的结果来交换俩个元素的位置，以此来达到排序的目的。
#### 1. 冒泡排序
    冒泡排序是最简单的一种交换排序，以升序为例，核心思想为：
    1. 从第一个元素开始，比较相邻的俩个元素。如果第一个比第二个大，则进行交换。
    2. 第一组结束后，轮到下一组继续比较交换，直到没有相邻的元素可以比较为止，此时最后一位是最大的数，就不用再比较了。
    3. 每次比完，大的数就像冒泡一样，飘到最后几位上，直到全部排好。排序结束。
![输入图片说明](img/maopao.gif)

##### 1.1 Java代码实现
```
// 冒泡排序
public static void maopao(int[] array) {
    // 当前数组的长度
    int arrLength = array.length - 1;
    int len;
    for (len = arrLength; len >= 0; len--) {
        for (int i = 0; i < len; i++) {
            if (array[i] > array[i + 1]) {
                int swap = array[i];
                array[i] = array[i + 1];
                array[i + 1] = swap;
            }
        }
    }
}
```
##### 1.2 时间复杂度
    冒泡排序算法每一轮都要遍历所有的元素，轮转的次数和数量是一样的，所以时间复杂度是O(N^2)
##### 1.3 空间复杂度
    冒泡排序算法排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)     

#### 2. 快速排序
    快速排序是从冒泡排序的算法演变而来的，在冒泡排序上进行了递归分治法。
	快速排序的思想很简单，就是先把待排序的数组拆成左右两个区间，左边都比中间的基准数小，右边都比基准数大。接着左右两边各自再做同样的操作，完成后再拆分再继续，一直到各区间只有一个数为止。

	举个例子，现在我要排序 4、9、5、1、2、6 这个数组。一般取首位的 4 为基准数，第一次排序的结果是：

	2、1、4、5、9、6

	可能有人觉得奇怪，2 和 1 交换下位置也能满足条件，为什么 2 在首位？这其实由实际的代码实现来决定，并不影响之后的操作。以 4 为分界点，对 2、1、4 和 5、9、6 各自排序，得到：

	1、2、4、5、9、6

	不用管左边的 1、2、4 了，将 5、9、6 拆成 5 和 9、6，再排序，至此结果为：

	1、2、4、5、6、9

	为什么把快排划到交换排序的范畴呢？因为元素的移动也是靠交换位置来实现的。算法的实现需要用到递归（拆分区间之后再对每个区间作同样的操作）
![输入图片说明](img/kuaisu.gif)
	
##### 2.1 Java代码实现
```
    // 快速排序
    public static void kuaisu(int[] array) {
        long start = System.nanoTime();
        sort(array, 0, array.length - 1);
        long end = System.nanoTime();
        System.out.println(end - start);

        long start1 = System.nanoTime();
        sort1(array, 0, array.length - 1);
        long end1 = System.nanoTime();
        System.out.println(end1 - start1);
    }

    // 优化前
    private static void sort1(int[] arr, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return;
        }
        int left = startIndex; // 左指针
        int right = endIndex; // 右指针
        int pivot = arr[startIndex]; // 基准元素
        int index = startIndex; // 基准index

        // 外循环在左右指针重合时结束
        while (right > left) {
            // right指针从右至左进行比较
            while (right > left) {
                // 基准元素大于右边指针元素
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }

            // left指针从左至右进行比较
            while (right > left) {
                // 基准元素大于右边指针元素
                if (arr[left] > pivot) {
                    arr[right] = arr[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[index] = pivot;
        sort1(arr, startIndex, index - 1);
        sort1(arr, index + 1, endIndex);
    }

    // 优化后
    private static void sort(int[] array, int low, int high) {
        int i, j, index;
        if (low > high) {
            return;
        }
        i = low; // 哨兵i
        j = high; // 哨兵j
        index = array[i]; // 第一次排序的基准数
        while (i < j) { // 从表的俩端往中间开始扫描
            while (i < j && array[j] >= index)
                j--;
            if (i < j)
                array[i++] = array[j];
            while (i < j && array[i] < index)
                i++;
            if (i < j)
                array[j--] = array[i];
        }
        array[i] = index;
        sort(array, low, i - 1);
        sort(array, i + 1, high);
    }
```

##### 2.2 时间复杂度
    快速排序算法在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止，平均情况下需要logn轮，
    因此快速排序算法的平均时间复杂度是O(nlogn)
    在极端情况下，快速排序算法每一轮只确定基准元素的位置，时间复杂度为O(N^2)

##### 2.3 空间复杂度
    O(logn)