# sort-test

**Repository Path**: wang_chin/sort-test

## Basic Information

- **Project Name**: sort-test
- **Description**: 基础排序
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-03-17
- **Last Updated**: 2021-06-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 常用排序算法

（*图片来源：https://www.cnblogs.com/onepixel/p/7674659.html*）

![sort](readme.assets/sort.png) 

![img](readme.assets/849589-20180402133438219-1946132192.png)

### 1.冒泡排序

#### 算法步骤：

- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。

#### 代码实现：

```java
public static void sort(int[] nums){
        if (nums == null){
            return;
        }
        int swap;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length-i-1; j++) {
                if(nums[j]>nums[j+1]){
                    swap = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = swap;
                }
            }
        }

    }
```

### 2.选择排序

选择排序就是在表中找到最小的数据，并放在表中开头的位置

#### 算法描述：

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。

#### 代码实现：

````java
public static void sort(int[] nums){
        if(nums == null){
            return;
        }
        int minIndex;
        int swap;
        for (int i = 0; i < nums.length; i++) {
            //每次都将最小索引置为i
            minIndex = i;
            for (int j = i; j < nums.length; j++) {
                if(nums[j]<nums[minIndex]){
                    minIndex = j;
                }
            }
            swap = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = swap;
        }
    }
````

### 3.插入排序

插入排序是从第二位开始，将其插入合适的位置，依次重复这个过程，直到最后一位。

#### 算法描述：

- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。

#### 代码实现：

````java
public static void sort(int[] nums){
        if(nums == null){
            return;
        }
        int swap;
        int index;
        for (int i = 1; i < nums.length; i++) {
            //每次将swap放入合适的位置
            swap = nums[i];
            index = i -1;
            //如果swap小，则向前找，并将元素向后移动
            while (index >= 0 && swap < nums[index]){
                nums[index+1] = nums[index];
                index--;
            }
            nums[index+1] = swap;
        }
    }
````

### 4.希尔排序

希尔排序是在插入排序的基础上进行的一个优化，插入排序每次都会将大（或较小）的元素向后移动，希尔排序通过分组的形式，在每组中做插入排序，然后减小分组个数，最后直至1为止。

#### 算法描述：

- 最初的分组为length/2，之后在此基础上除以2取整
- 循环内部使用插入排序

#### 算法实现：

````java
   public static void sort(int[] nums){
        if(nums == null){
            return;
        }
        for (int gap = nums.length/2; gap >= 1; gap=gap/2) {
            //内部是插入排序
            int swap;
            int index;
                for (int i = gap; i < nums.length; i++) {
                swap = nums[i];
                //和插入排序不同的是，此处下标移动的大小是分组的大小
                index = i -gap;
                while (index >= 0 && swap < nums[index]){
                    nums[index+gap] = nums[index];
                    index-=gap;
                }
                nums[index+gap] = swap;
            }
        }
    }
````

### 5.归并排序

​	使用分治算法（分而治之），将已有序的子序列[合并](https://baike.baidu.com/item/合并/5615281)，得到完全有序的[序列](https://baike.baidu.com/item/序列/1302588)；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为[二路归并](https://baike.baidu.com/item/二路归并/53201558)（来自百度百科）。

#### 算法描述：

第一步：申请空间，使其大小为两个已经[排序](https://baike.baidu.com/item/排序)序列之和，该空间用来存放合并后的序列

第二步：设定两个[指针](https://baike.baidu.com/item/指针)，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

#### 实现：

````java
public static int[] sort(int[] nums, int index, int size) {
        if (size < 2) {
            return new int[]{nums[index]};
        }
        int middle = size / 2;
        int[] left = sort(nums, index, middle);
        int[] right = sort(nums, index + middle , size - middle);
        return merge(left, right);
    }

    private static int[] merge(int[] left, int[] right) {
        int[] mergeNums = new int[left.length + right.length];
        int l = 0, r = 0;
        while (l < left.length || r < right.length) {
            if (l < left.length && (r == right.length || left[l] < right[r])) {
                mergeNums[l + r] = left[l];
                l++;
            } else if (r < right.length && (l == left.length || left[l] > right[r])) {
                mergeNums[l + r] = right[r];
                r++;
            }
        }
        return mergeNums;
    }
````