简单的三种排序算法原理及其优缺点_简单选择排序的优缺点

选择排序法：

概念：
选择排序是不稳定的排序方法。

首先在数组中找到最小（大）元素，存放到序列的起始位置，再从剩余的元素中找最小（大）的元素，然后将他接着存到上个已经经过排列的元素后面，循环至所有的元素都排列完毕。

优点：移动数据的次数已知（n-1次）；
缺点：比较次数多。

public static void xuanze(int arr[]){
    int temp = 0;
    for(int i =0; i < arr.length -1; i++){
        // 记录最小数的下标
        int minIndex = i;
        for(int j = i + 1; j< arr.length; j++){
            if(arr{minIndex} > arr[j]){
                // 修改最小值的下标
                minIndex = j;
            }
        }
        if(i != minIndex){
            // 根据下标换位
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

冒泡排序法

概念：
冒泡排序是一种较简单的排序算法。

他是依次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。

优点：稳定；
缺点：慢，每次只能移动相邻两个数据。

public static void maopao(int[] arr){
    int temp = 0;
    // 外层的循环，决定一共运行几次
    for (int i = 0; i < arr.length - 1; i++){
        // 内层循环，决定每次执行外层循环运行几次
        for(int j = 0; j < arr.length -i -1; ++j){
            // 如果后一个大于前一个
            if(arr[j + 1] < arr[j]){
                // 换位
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        } 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

插入排序法

插入排序是一种简单直观的排序算法。

一个无序的数组，或者一段需要排序的序列，我们通常用第一个元素作为参考值，从第二个元素开始和这个参考值进行比较，比这个参考值大的时候放在这个参考值的后面，比这个参考值小的时候在和这个参考值的前一位进行比较，当比较至适当位置进行插入。

优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

/**
  * 插入排序法
  *
  * @author xx 
  */
public static void charu(int arr[]){
    int i, j;
    for(i = 1; i <arr.length; i++){
        int temp = arr[i];
        for(j = i; j > 0 && temp < arr[j -1]; j--){
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15