抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

算法|排序

算法

发布于：2024年3月19日

认识位运算符

获取整数的二进制32位字符

1
2
3
4
5
6
public static void print(int num) {
    for (byte i = 31; i >= 0; i--) {
        System.out.print((num & (1 << i)) == 0 ? "0" : "1");
    }
    System.out.println();
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
byte a = 43;
byte b = 120;
System.out.print("a  :");print(a); 			//a  :00101011
System.out.print("b  :");print(b);			//b  :01111000
System.out.print("a|b:");print(a | b);		//a|b:01111011
System.out.print("a&b:");print(a & b);		//a&b:00101000
System.out.print("a^b:");print(a ^ b);		//a^b:01010011
System.out.print(" ~b:");print(~b);			// ~b:10000111
System.out.print("135:");print(135);		//135:10000111
System.out.print("a  :");print(a);			//a  :00101011
System.out.print("<<3:");print(a<<3);		//<<3:01011000
System.out.print(">>1:");print(a>>1);		//>>1:00010101
System.out.print(">>>1:");print(a>>>1);		//>>>1:00010101
System.out.println(~b);						//-121
print(~b>>7);								//11111111

|：或

1
2
3
4
//00101011
//01111000
//01111011
print(43 | 120);	//01111011

有1为1

&：与

1
2
3
4
//00101011
//01111000
//00101000
print(43 & 120);	//00101000

有0为0

^：亦或

1
2
3
4
//00101011
//01111000
//01010011
print(43 ^ 120);	//01010011

无进位相加

~：非

取反

1
2
3
4
//01111000
//10000111
print(~120);	//10000111
print(135);		//10000111

~120和135的字符是一样的，为什么它是-121不是135呢？

首先理解，byte 占 8位（-128-127），其中[符号位]占一位，其余数据占用

其次当一个数是负数的时候，符号位以及其左边的位置，均为1。也就是说，-121是//1111....110000111，而135是//0000.....010000111

最后，~操作可以理解成在一条直线上，从[0和-1的中间位置]反方向去找到第n个点

注意：在程序中，0算正数。后文会验证这一结论。

<<：左移

1
2
print(43);			//00101011
print(43<<3);		//01011000

>>：右移

1
2
print(43);			//00101011
print(43>>1);		//00010101

>>>：无符号右移

1
2
3
print(43>>>1);		//00010101
print(~120);		//10000111
print(~120>>7);		//11111111

正数>>> 等价 >>

常见使用

  1. 判断奇偶性

    1
    (num & 1) == 1 ? "奇数" : "偶数"

  2. 两个数做交换

    1
    2
    3
    4
    5
    6
    7
    8
    9
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    // 注意：在数组操作中时，切记不能进行用位置亦或，不然数据会丢失

    //可以简化成
    a ^= b;
    b ^= a;
    a ^= b;

  3. 取绝对值

    1
    2
    int b = -327
    int a = (b ^ (b>>31)) - (b>>31);

  4. 判断两个数是否异号

    1
    2
    3
    4
    5
    6
    boolean f = ((x ^ y) < 0);
    // 同号false，异号true

    // boolean f = ((0 ^ 1) < 0);
    // System.out.println(f);
    // 结果是false

  5. 大小写转换

    1
    2
    3
    4
    5
    6
    // ('A' | ' ') = 'a'
    // ('a' | ' ') = 'a'
    // ('A' & '_') = 'A'
    // ('a' & '_') = 'A'
    // ('A' ^ ' ') = 'a'
    // ('a' ^ ' ') = 'A'

  6. +1

    1
    2
    int n = 10;
    n = -~n;

  7. -1

    1
    2
    int n = 10;
    n = ~-n;

排序

排序动态展示（冒泡排序，选择排序，插入排序，归并排序，快速排序，计数排序，基数排序） - VisuAlgo

打印

1
Arrays.stream(arr).forEach(a-> System.out.print(a + " "));

交换

1
2
3
4
5
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[j];
    arr[j] = arr[i];
    arr[i] = tmp;
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    for (int i = 0; i < N; i++) {
        int minValueIndex = i;
        for (int j = i + 1; j < N; j++) {
            minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
        }
        swap(arr, i, minValueIndex);
    }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    for (int end = N - 1; end >= 0; end--) {
        for (int second = 1; second <= end; second++) {
            if (arr[second - 1] > arr[second]) {
                swap(arr, second - 1, second);
            }
        }
    }
}

插入排序

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
public static void insertSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    for (int end = 1; end < N; end++) {
        int newNumIndex = end;
        while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
            swap(arr, newNumIndex - 1, newNumIndex);
            newNumIndex--;
        }
    }
}

public static void insertSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    for (int end = 1; end < N; end++) {
        for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
            swap(arr, pre, pre + 1);
        }
    }
}

归并排序

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
public static void mergeSort(int[] arr, int left, int right) {
    if (left == right) return;
    //分成两半
    int mid = left + (right-left)/2;
    //左边排序
    mergeSort(arr, left, mid);
    //右边排序
    mergeSort(arr, mid+1, right);

    merge(arr, left, mid+1, right);
}

static void merge(int[] arr, int leftPtr, int rightPtr, int rightBound) {
    int mid = rightPtr - 1;
    int[] temp = new int[rightBound - leftPtr + 1];

    int i = leftPtr; 
    int j = rightPtr;
    int k = 0;

    while(i <= mid && j <= rightBound) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }

    while(i<=mid) temp[k++] = arr[i++];
    while(j<=rightBound) temp[k++] = arr[j++];

    for(int m=0; m<temp.length; m++) arr[leftPtr +m] = temp[m];

}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void quickSort(int[] arr, int leftBound, int rightBound) {
    if(leftBound >= rightBound) return;
    int mid = partition(arr, leftBound, rightBound);
    quickSort(arr, leftBound, mid-1);
    quickSort(arr, mid+1, rightBound);
}

static int partition(int[] arr, int leftBound, int rightBound) {
    //adding the following code blocks is the random quick sort
    {
        int random = leftBound + (int) (Math.random() * (rightBound - leftBound + 1));
        swap(arr, random, rightBound);
    }
    int pivot = arr[rightBound];
    int left = leftBound;
    int right = rightBound - 1;
    while(left <= right) {
        while(left <= right && arr[left] <= pivot) left ++;
        while(left <= right && arr[right] > pivot) right --;
        if(left < right) BaseCoding.swap(arr, left, right);
    }
    BaseCoding.swap(arr, left, rightBound);
    return left;
}

计数排序

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
/**
 * 计数排序：
 * 遍历源数组找到最大值，通过这最大值创建一个计数数组；
 * 遍历源数组，在计数数组，源数组值位置，++；
 * 遍历计数数组，将数值大于0位置，以此写入源数组。
 *
 * @param arr 原数组
 */
public static void countSort(int[] arr) {
    if (arr == null || arr.length < 2) return;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int[] bucket = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }
    int i = 0;
    for (int j = 0; j < bucket.length; j++) {
        while (bucket[j]-- > 0) {
            arr[i++] = j;
        }
    }
}

堆排序

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
49
50
/**
 * 堆排序:
 *
 * @param arr 源数组
 */
public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) return;
    // O(N*logN)
    // for (int i = 0; i < arr.length; i++) {
    //	 heapInsert(arr, i);
    // }
    // O(N)
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    // O(N*logN)
    while (heapSize > 0) {
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);
    }
}

private static void heapify(int[] arr, int index, int heapSize) {
    int left = (index << 1) + 1;
    while (left < heapSize) { // 下方还有孩子的时候
        // 两个孩子中，谁的值大，把下标给largest
        // 1）只有左孩子，left -> largest
        // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
        // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父和较大的孩子之间，谁的值大，把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = (index << 1) + 1;
    }

}

private static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

基数排序

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
49
50
51
/**
 * 基数排序
 * @param arr
 */
public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

private static int maxbits(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int res = 0;
    while (max != 0) {
        res++;
        max /= 10;
    }
    return res;
}

private static void radixSort(int[] arr, int L, int R, int digit) {
    final int radix = 10;
    int i = 0, j = 0;
    int[] help = new int[R - L + 1];
    for (int d = 1; d <= digit; d++) {
        int[] count = new int[radix]; // count[0..9]
        for (i = L; i <= R; i++) {
            j = getDigit(arr[i], d);
            count[j]++;
        }
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        for (i = R; i >= L; i--) {
            j = getDigit(arr[i], d);
            help[count[j] - 1] = arr[i];
            count[j]--;
        }
        for (i = L, j = 0; i <= R; i++, j++) {
            arr[i] = help[j];
        }
    }
}

public static int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://solitaire-12.github.io/2024/03/19/algorithm/sort/

更新于：2024年3月19日

排序

评论