# algorithm

**Repository Path**: mslace/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: 算法的探索
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2017-07-05
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 排序

### SelectionSort选择排序 O(n^2)

8 6 2 3 1 5 7 4

> 思路 找最小的数据和还没进行排序的数组的第一个数据进行替换

1. ==1== 6 2 3 ==8== 5 7 4
2. 1 6 2 3 8 5 7 4
3. 1 ==2== ==6== 3 8 5 7 4
4. 1 2 6 3 8 5 7 4
5. 1 2 ==3== ==6== 8 5 7 4
6. 1 2 3 6 8 5 7 4
7. 1 2 3 ==4== 8 5 7 ==6==
8. 1 2 3 4 8 5 7 6
9. 1 2 3 4 ==5== ==8== 7 6
10. 1 2 3 4 5 8 7 6
11. 1 2 3 4 5 ==6== 7 ==8==
12. 1 2 3 4 5 6 7 8

```java
 public void selectionSort(Integer[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            //从i开始往后找还没排序的数组中最小的数
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //把最小的数和第一个数据进行替换
            Integer temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
 }
```
> 这里有几个优化点。

1. 首先如果i位置的元素就是最小元素则无需进行交换操作

```java
 public void selectionSort(Integer[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            //从i开始往后找还没排序的数组中最小的数
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //把最小的数和第一个数据进行替换
            //优化1
            if(i!=minIndex){
            Integer temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            }
        }
 }
```
2. 为了提升效率,我们同时选出最大最小值，放置在数组左右两边
![image](http://img.blog.csdn.net/20161123222123116)
```java
public void selectionSortDouble(Integer[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int min = left;
            int max = right;
            //循环中找到最大和最小值的索引
            for (int i = left; i <= right; i++) {
                if (arr[i] < arr[min]) min = i;
                if (arr[i] > arr[max]) max = i;
            }
            //最大值放在最右边
            Integer tmp1 = arr[right];
            arr[right] = arr[max];
            arr[max] = tmp1;
            //
            if (min == right) min = max;
            //最小值放在最左边
            Integer tmp2 = arr[left];
            arr[left] = arr[min];
            arr[min] = tmp2;
            right--;
            left++;
        }
}
```

### InsertSort插入排序 O(n^2)

8 6 2 3 1 5 7 4

> 思路 从第二个元素开始，寻找还已进行排序的数组的合适位置，插入该元素

1. ==6== ==8== 2 3 1 5 7 4
2. ==2== ==6== ==8== 3 1 5 7 4
3. ==2== ==3== ==6== ==8== 1 5 7 4
4. ==1== ==2== ==3== ==6== ==8== 5 7 4
5. ==1== ==2== ==3== ==5== ==6== ==8== 7 4
6. ==1== ==2== ==3== ==5== ==6== ==7== ==8== 4
7. ==1== ==2== ==3== ==4== ==5== ==6== ==7== ==8==

```java
public void insertionSort(Integer[] arr) {
        int n = arr.length;
        int tmp;
        for (int i = 1; i < n; i++) {
            // 待插入数据
            tmp = arr[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                // 判断是否大于tmp，大于则后移一位
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
}
```

### BublleSort插入排序 O(n^2)


### ShellSort插入排序 O(n^1.3)
![image](http://images2015.cnblogs.com/blog/1024555/201611/1024555-20161128110416068-1421707828.png)
```java
public void shellSort(Integer[] arr) {
        //将数组的步长二分衰减
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //将分离gap位置的数组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = 0;
                int tmp = arr[i];
                for (j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > tmp) {
                        arr[j + gap] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + gap] = tmp;
            }
        }
}
```