排序算法

排序

定义:
    将一组无序的元素,按照某种方式排列(通常是按照大小或者字母顺序),排序后索引较大的元素大于等于索引较小的元素
PS:
    这里为了方便起见,所有元素都选择数字类型

1. 选择排序

思路:
    首先,找到数组最小的元素,将其与数组的第一个元素交换位置,然后从剩下的元素中找出最小的元素,并与剩下元素的第一个元素(即第二个元素)交换,如此往复,直到整个数组排序完毕

代码实现

/** 选择排序 */
public static void selectSort(int[] arrs) {
   int length = arrs.length;
   for (int i = 0; i < length - 1; i++) {
       int minIndex = i;
       for (int j = i + 1; j < length; j++) {
           if (arrs[j] < arrs[minIndex]) {
               // 将最小元素下标记录
               minIndex = j;
           }
       }
       // 将最小元素与当前剩余元素的第一位交换
       swap(arrs, i, minIndex);
   }
}   

2. 插入排序

思路:
    假设前面的部分是有序的,然后将其余的元素插入之前有序元素的适当位置

代码实现

/**
* 插入排序
*/
public static void insertSort(int[] arrs) {
   int length = arrs.length;
   for (int i = 1; i < length; i++) {
       for (int j = i; j > 0; j--) {
           if (arrs[j] < arrs[j - 1]) {
               swap(arrs, j, j - 1);
           } else {
               break;
           }
       }
   }
}

3. 冒泡排序

思路:
    对比相邻的2个元素,如果顺序错误就交换,然后重复查询直到没有在需要交换的

代码实现

/**
* 冒泡排序
*/
public static void bubbleSort(int[] arrs) {
  int length = arrs.length;
  for (int i = 0; i < length; i++) {
      for (int j = 0; j < length - i - 1; j++) {
          if (arrs[j] > arrs[j + 1]) {
              swap(arrs, j, j + 1);
          }
      }
  }
}

4. 快速排序

思路:
    选定一个基准点,对所有数据进行切分,左右2边分别为比基准点大或小的,循环操作,来达到排序的目的
    
选中一个基数,从两端开始探测,先从右至左,找出一个小于 基数的数,再从左至右找一个大于基数的数,交换,然后递归交换, 交换到最后的时候,将基数与左边数组中最后一位交换即可

代码实现

 /**
     * 快速排序
     */
    public static void quickSort(int[] arrs) {
        quickSort(arrs, 0, arrs.length - 1);

    }

    private static void quickSort(int[] arrs, int l, int r) {
        if (l > r) {
            return;
        }

        int i, j, temp;
        temp = arrs[l];

        i = l;
        j = r;

        while (i != j) {
            while (arrs[j] >= temp && i < j) {
                j--;
            }
            while (arrs[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                swap(arrs, i, j);
            }
        }

        arrs[l] = arrs[i];
        arrs[i] = temp;

        quickSort(arrs, l, i-1);
        quickSort(arrs, i+1, r); 
    }