常用排序算法kotlin实现

冒泡排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/***
 *
 *         平均O(n^2)最坏O(n^2)最优O(n) 辅助空间O(1)  稳定
 */
private fun bubbleSort(sortList: IntArray) {
    var didSwap: Boolean
    for (i in 0 until sortList.size - 1) {
        didSwap = false
        for (j in 0 until sortList.size - 1 - i) {
            if (sortList[j] > sortList[j + 1]) {
                swapByIndex(sortList, j, j + 1)
                didSwap = true
            }
        }
        if (!didSwap) {
            return
        }
    }
}

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/***
 *
 *         平均O(n^2)最坏O(n^2)最优O(n) 辅助空间O(1)  稳定
 */
private void bubbleSort(int[] arr, int n) {
    boolean flag;
    for (int i = 1; i < n; i++) {
        flag = false;
        for (int j = 0; j < n - i; j++) {
            if (arr[j] < arr[j + 1]) {
                swapByIndex(arr, j, j + 1);
            }
        }
        if (!flag) break;
    }
}

快速排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/***
 *          平均O(n log n)最优O(n log n)最坏O(n^2) 辅助空间O(log n)~ O(n) 不稳定
 */
private fun quickSort(sortList: IntArray) {
    loopForQuickSort(sortList, 0, sortList.size - 1)
}
	
private fun loopForQuickSort(list: IntArray, start: Int, end: Int) {
    if (start >= end) {
        return
    }
    val k = partition(list, start, end)
    loopForQuickSort(list, start, k - 1)
    loopForQuickSort(list, k + 1, end)
}

private fun partition(list: IntArray, begin: Int, end: Int): Int {
    val x = list[end]
    var i = begin - 1

    for (j in begin until end) {
        if (list[j] <= x) {
            i++
            swapByIndex(list, i, j)
        }
    }

    swapByIndex(list, end, i + 1)

    return i + 1
}

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/***
 *          平均O(n log n)最优O(n log n)最坏O(n^2) 辅助空间O(log n)~ O(n) 不稳定
 */
private void sort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private void quickSort(int[] arr, int begin, int end) {
    if (begin >= end)
        return;

    int k = partition(arr, begin, end);
    quickSort(arr, begin, k - 1);
    quickSort(arr, k + 1, end);
}

private int partition(int[] arr, int begin, int end) {
    int x = arr[end];
    int i = begin - 1;

    for (int j = begin; j < end; j++) {
        if (arr[j] <= x) {
            i++;
            swapByIndex(arr, i, j);
        }
    }

    swapByIndex(arr, end, i + 1);

    return i + 1;
}

选择排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 /***
 *         平均O(n^2)最坏O(n^2)最优O(n^2) 辅助空间O(1) 不稳定
 *         效率差，但是可以用在“取出数列中最大/最小的几个值”的情况
 */
private fun selectionSort(sortList: IntArray) {
    for (i in 0..sortList.size - 2) {
        var minIndex = i
        for (j in i + 1 until sortList.size - 1) {
            if (sortList[minIndex] > sortList[j]) {
                //找到比较小的值的索引
                minIndex = j
            }
        }
        swapByIndex(sortList, i, minIndex)
    }
}

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 /***
 *         平均O(n^2)最坏O(n^2)最优O(n^2) 辅助空间O(1) 不稳定
 *         效率差，但是可以用在“取出数列中最大/最小的几个值”的情况
 */
private void selectSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swapByIndex(arr, minIndex, i);
        }
    }
}

插入排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/***
 *       平均O(n^2)最坏O(n^2)最优O(n) 辅助空间O(1) 稳定
 *       可以解决两个有序列表的合并问题，将第二个序列放在第一个序列后面，进行选择插入排序即可
 */
private fun insertSort(sortList: IntArray) {
    for (i in 1 until sortList.size) {
        for (j in i downTo 1) {
            if (sortList[j] > sortList[j - 1]) {
                //已经找到当前元素要插入的位置
                break
            }
            swapByIndex(sortList, j - 1, j)
        }
    }
}

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/***
 *       平均O(n^2)最坏O(n^2)最优O(n) 辅助空间O(1) 稳定
 *       可以解决两个有序列表的合并问题，将第二个序列放在第一个序列后面，进行选择插入排序即可
 */
private void insertSort(int[] arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                swapByIndex(arr, j, j - 1);
            } else {
                break;
            }
        }
    }
}

希尔排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/***
  *         平均O(n log n)最坏O(n log^2 n)最优O(n log^2 n) 辅助空间O(1) 不稳定
  */
 private fun shellSort(sortList: IntArray) {
     var gap = 1
     while (gap < sortList.size / 3) {
         //寻找合适的步长
         gap = gap * 3 + 1
     }
     while (gap > 0) {
         for (i in gap until sortList.size) {
             val temp = sortList[i]
             var j = i - gap
             while (j >= 0) {
                 //将以temp为元素起点，以gap为步进长度构成的list进行插入运算
                 if (sortList[j] <= temp) {
                     break
                 }
                 sortList[j + gap] = sortList[j]
                 j -= gap
             }
             sortList[j + gap] = temp
         }
         gap /= 3
     }
 }

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/***
  *         平均O(n log n)最坏O(n log^2 n)最优O(n log^2 n) 辅助空间O(1) 不稳定
  */
 private void shellSort(int arr[], int length) {
     int temp = 0;
     int incre = length;

     while (true) {
         incre = incre / 2;
         //对分组进行遍历
         for (int i = 0; i < incre; i++) {
             //插入排序
             for (int j = i + incre; j < length; j += incre) {
                 for (int k = j; k > i; k -= incre) {
                     if (arr[k] < arr[k - incre]) {
                         swapByIndex(arr, k, k - incre);
                     } else {
                         break;
                     }
                 }
             }
         }
         //无法分组，表示排序结束
         if (incre == 1) {
             break;
         }
     }
 }

堆排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/***
 *         平均O(n log n)最坏O(n log n)最优O(n log n) 辅助空间O(1) 不稳定
 *
 */
private fun heapSort(sortList: IntArray) {
    val len = sortList.size
    for (i in len / 2 - 1 downTo 0) {
        //这一步的作用就是建立最大堆模型
        //这里选出来的i，就是当前堆的最后一个三角的单位中的爸爸，也就是说从最后一个单元开始向上递增构建最大堆
        loopForHeap(sortList, i, len)

    }
    for (i in len - 1 downTo 1) {
        //依次拿出堆顶元素放在数列最后
        swapByIndex(sortList, 0, i)
        //对剩余的0-->i的堆重拍，即可找到剩余数列中的最大值
        loopForHeap(sortList, 0, i)
    }
}
	
 private fun loopForHeap(list: IntArray, start: Int, end: Int) {
    if (start >= end) {
        return
    }
    val dad = start
    var son = dad * 2 + 1
    if (son >= end) {
        //儿子索引已经超过数组最大索引
        return
    }
    if (son + 1 < end && list[son] < list[son + 1]) {
        //说明两个儿子之间右边的更大
        son++
    }
    if (list[dad] <= list[son]) {
        //交换父子
        swapByIndex(list, dad, son)
        //因为父子交换了，因此该分支下面所有堆都要重排
        //并且索引从当前换位的son开始直到该分支最后一位元素
        loopForHeap(list, son, end)
    }
}

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/***
 *         平均O(n log n)最坏O(n log n)最优O(n log n) 辅助空间O(1) 不稳定
 *
 */
private void MinHeap_Sort(int a[], int n) {
    int temp = 0;
    MakeMinHeap(a, n);

    for (int i = n - 1; i > 0; i--) {
        swapByIndex(arr, 0, i);
        MinHeapFixdown(a, 0, i);
    }
}


private void MakeMinHeap(int a[], int n) {
    //从倒数第二层开始排序，取自己的孩子进行排序，这样所有的节点都排序到了
    for (int i = (n - 1) / 2; i >= 0; i--) {
        MinHeapFixdown(a, i, n);
    }
}


private void MinHeapFixdown(int a[], int i, int n) {

    int j = 2 * i + 1; //左节点
    int temp = 0;

    //j<n：如果左节点小于节点总数，表示该节点有节点，否则该节点是叶子节点是不需要调整的
    while (j < n) {
        //j+1<n：存在右节点，a[j+1]<a[j]：左右子节点中寻找最小的
        if (j + 1 < n && a[j + 1] < a[j]) {
            //将节点移到右节点
            j++;
        }

        //较大节点在下面
        if (a[i] <= a[j])
            break;

        //较大节点在上面，则将大节点下移
        swapByIndex(arr, i, j);

        //复位
        i = j;
        j = 2 * i + 1;
    }
}

基数排序

kotlin版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/***
 *         平均O(d*(n+r))最坏O(d*(n+r))最优O(d*(n+r)) 辅助空间O(n+r) 稳定
 *         d 为位数，r 为基数，n 为原数组个数
 */
private fun radixSort(sortList: IntArray) {
    //寻找当前序列中的最大值，目的是计算最大的位数
    var max = 0
    for (i in 0 until sortList.size - 1) {
        if (sortList[i] > max) {
            //找到当前序列最大数
            max = sortList[i]
        }
    }
    //通过最大数找到最大数的位数
    val maxDigit = max.toString().length
    var mod = 10
    var dev = 1
    for (i in 0 until maxDigit) {
        val counter = mutableMapOf<Int, ArrayList<Int>>()
        for (j in 0 until sortList.size) {
            // 取出某个数的第mod位的值
            // 比如数字123，123%100=23,23继续计算23/10=2，最终拿到123的中间位数字
            val bucket = (sortList[j] % mod) / dev
            //按照当前位数作为key以此存入counter的map中
            if (counter[bucket] == null) {
                counter[bucket] = ArrayList<Int>()
            }
            counter[bucket]?.add(sortList[j])
        }
        var pos = 0
        for (i in 0..9) {
            //这里一定使用0--9的索引，因为对counter来说，里面的map的key只能是这个组合，并且一定要按照从0到9的顺序弹出
            counter[i]?.forEach {
                //依次将counter中的值放入列表中
                //第一次经过进--出的操作就对个位数字进行了排序
                //第二次经过进--出的操作就对十位进行了排序
                //经过上面两次排序，就达到了个位+十位的综合排序，也就完成了两位数字的整体排序
                sortList[pos++] = it
            }
        }
        dev *= 10
        mod *= 10
    }
}

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/***
 *         平均O(d*(n+r))最坏O(d*(n+r))最优O(d*(n+r)) 辅助空间O(n+r) 稳定
 *         d 为位数，r 为基数，n 为原数组个数
 */
private void radixSort(int[] array, int d) {
    int n = 1;//代表位数对应的数：1,10,100...
    int k = 0;//保存每一位排序后的结果用于下一位的排序输入
    int length = array.length;
    int[][] bucket = new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
    int[] order = new int[length];//用于保存每个桶里有多少个数字
    while (n < d) {
        for (int num : array) //将数组array里的每个数字放在相应的桶里
        {
            int digit = (num / n) % 10;
            bucket[digit][order[digit]] = num;
            order[digit]++;
        }
        for (int i = 0; i < length; i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
        {
            if (order[i] != 0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
            {
                for (int j = 0; j < order[i]; j++) {
                    array[k] = bucket[i][j];
                    k++;
                }
            }
            order[i] = 0;//将桶里计数器置0，用于下一次位排序
        }
        n *= 10;
        k = 0;//将k置0，用于下一轮保存位排序结果
    }

}

交换位置

1
2
3
4
5
private fun swapByIndex(list: IntArray, x: Int, y: Int) {
    val temp = list[x]
    list[x] = list[y]
    list[y] = temp
}