排序算法

1、冒泡排序

排序规则：
时间复杂度：O(n²)
冒泡排序算法（从后往前）规则：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现：

package com.thread.test;

/**
 * 冒泡排序算法
 *
 * @author tangyifei
 * @date 2019年9月4日11:05:55
 */
public class Test1 {
    public static void main(String[] args) {
        int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50, 2, 33, 12, 10};
        int len = arr.length - 1;
        System.out.println("排序前");
        print(arr);
        System.out.println("排序后");
        for(int i = 0; i <= len; i++) {
            // 这里注意一定是j < len-i；不是j <= len-i，不然会报数组越界异常
            for(int j = 0; j < len - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }

        }
        print(arr);
    }

    public static void print(int arr[]) {
        int len = arr.length;
        StringBuilder sb = new StringBuilder(len);
        sb.append("[");
        for(int i = 0; i < len; i++) {
            if (i == len - 1) {
                sb.append(arr[i]).append("]");
            } else {
                sb.append(arr[i]).append(",");
            }
        }
        System.out.println(sb.toString());

    }
}

打印的结果：
排序前
[51,46,20,18,65,97,82,30,77,50,2,33,12,10]
排序后
[2,10,12,18,20,30,33,46,50,51,65,77,82,97]

2、选择排序

排序规则：
时间复杂度：O(n²)
选择排序（Selection sort）同样也是最经典最简单的排序算法之一，特点就是简单直观。
排序的原理：首先在未排序的序列里找到最小(大)元素，放到序列的首端，再从剩余元素中找到最小(大)的元素，放到序列的尾端。依次循环，直到排序完成。

代码实现：

package com.thread.test;

/**
 * 选择排序
 *
 * @author tangyifei
 * @date 2019年9月4日11:14:00
 */
public class Test2 {

    public static void main(String[] args) {
        int a[] = new int[]{10, 3, 5, 6, 8, 4, 9, 2, 1, 7};
        int len = a.length;
        System.out.println("排序前");
        print(a);
        System.out.println("排序后");
        // 每一个元素与数组中的后续元素一一比较
        for(int i = 0; i < len - 1; i++) {
            for(int j = i + 1; j < len; j++) {
                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;

                }

            }

        }
        print(a);

    }

    public static void print(int arr[]) {
        int len = arr.length;
        StringBuilder sb = new StringBuilder(len);
        sb.append("[");
        for(int i = 0; i < len; i++) {
            if (i == len - 1) {
                sb.append(arr[i]).append("]");
            } else {
                sb.append(arr[i]).append(",");
            }
        }
        System.out.println(sb.toString());

    }

}

运行结果如下：
排序前
[10,3,5,6,8,4,9,2,1,7]
排序后
[1,2,3,4,5,6,7,8,9,10]

二分查找法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
注意：二分查找前提条件是：该序列有序

package com.thread.test;

/**
 * 二分查找法
 *
 * @author tangyifei
 * @date 2019年9月4日11:14:00
 */
public class Test2 {

    public static void main(String[] args) {
        // 二分查找法一定要保证数组有序
        int a[] = new int[]{11, 22, 33, 44, 55, 66, 77};
        // 找22这个元素在有序的数组中的位置
        System.out.println(binarySearch(a, 22));

    }

    public static int binarySearch(int a[], int value) {
        int min = 0;
        int max = a.length - 1;
        // 中间的位置
        int mid = (min + max) >> 1;
        // 如果中间位置的元素不是我们要找的元素
        while (a[mid] != value) {
            // 判断中间位置的元素值是否大于我们要找的元素的值
            if (a[mid] > value) {
                // 如果中间位置的元素值大于我们要找的元素的值
                // 那么向中间位置左边的元素集合中去查找我们的元素
                max = mid - 1;
            } else if (a[mid] < value) {
                // 如果中间位置的元素值大于我们要找的元素的值
                // 那么向中间位置右边的元素集合中去查找我们的元素
                min = mid + 1;
            }
            mid = (min + max) >> 1;
        }
        if (min > max) {
            return -1;
        }
        return mid;
    }


}

其他的排序请参考这篇博客