Java排序算法

image.png

选择排序

每次循环找出最小数然后依次排序。
1、第0个数比对第1-N个数找到最小数，
2、第1个比对第2-N个数找到最二小数，
3、第2个比对第3-N个数找到最三小数，
。。。。

 /**
     * 选择排序
     *
     * @param array
     * @return
     */
    public static int[] selectSort(int[] array) {
        if (array == null || array.length == 0) {
            throw new NullPointerException("array is not null");
        }
        for (int i = 0, length = array.length; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                if (array[i] > array[j]) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

冒泡排序

对要排序的数据，从上到下依次比较两个相邻的数并加以调整，将最大的数向下移动，较小的数向上冒起。即：每一趟依次比较相邻的两个数据元素，将较小的数放在左边，循环进行同样的操作，直到全部待排序的数据元素排完.

第一趟排序

第一趟排序
第二趟排序

第二趟排序
第三趟。。。。

   /**
     * 冒泡排序bubble sort
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            throw new NullPointerException("array is not null");
        }
        for (int i = array.length - 1; i > 0; i--) {
            //比较length-1趟
            for (int j = 0; j < i; j++) {
                //比较相邻数字大小
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

插入排序

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
以数组{38,65,97,76,13,27,49}为例，

image.png

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

选择排序，冒泡排序，插入排序区别:
1、选择排序是一个比对整个数组找到最小值
2、冒泡排序，是比较隔壁找到最小值
3、插入排序，是比对一排，然后插入位置，后面往后移。

image.png

归并排序

/**
         * 归并排序
         * @param array IntArray
         * @param low Int
         * @param high Int
         */
        fun mergerSort(array: IntArray, low: Int, high: Int) {
            val mid: Int = (low + high) / 2
            if (low < high) {
                mergerSort(array, low, mid)
                mergerSort(array, mid + 1, high)
                merge(array, low, mid, high)
            }
        }

        private fun merge(array: IntArray, low: Int, mid: Int, high: Int) {
            var temp: IntArray = IntArray(high - low + 1)
            var i = low
            var j = mid + 1
            var k = 0
            while (i <= mid && j <= high) {
                if (array[i] < array[j]) {
                    temp[k] = array[i]
                    i++
                } else {
                    temp[k] = array[j]
                    j++
                }
                k++
            }
            while (i <= mid) {
                temp[k++] = array[i++]
            }
            while (j <= high) {
                temp[k++] = array[j++]
            }
            for (k2 in temp.indices) {
                array[k2 + low] = temp[k2]
            }
        }

快速排序

线性排序

桶排序：

桶排序比较适合用在外部排序中，所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中.(数值大小为整数，并相对不大)

计数排序

（数值大小为整数，并相对不大或者数值大小确定)

// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入 c 中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组 r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给 a 数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}