• 八大排序(尚未完善)


    基本的流程就不写了,不会就自己看代码,按照代码跑6、7遍就懂了

    java的数组值交换

    异或交换运算(需要保证位置不同):

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

    1. 冒泡排序

    时间复杂度O(N^2),额外空间复杂度O(1)

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

    2. 插入排序

    时间复杂度O(N^2),额外空间复杂度O(1)

    public static void insertionSort(int[] arr){
            if(arr == null || arr.length < 2)
                return;
            for(int i = 1; i < arr.length; i ++){
                for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){
                    swap(arr, j, j + 1);
                }
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    3. 选择排序

    // 选择排序
    	public static void selectSort(int[] arr){
    		if(arr == null || arr.length < 2)
    			return;
    		for(int i = 0; i < arr.length; i ++){
    			int minIndex = i;
    			for(int j = i; j < arr.length; j ++){
    				minIndex = arr[minIndex] < arr[j]? minIndex : j;
    			}
    			if(i == minIndex)
    				continue;
    			swap(arr, i, minIndex);
    		}
    		return;
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    4. 基数排序

    // 基数排序 daixie
    	public static void radixSort(int[] arr){
    		if(arr == null || arr.length < 2)
    			return;
    		radixSort(arr, 0, arr.length - 1, maxbits(arr));
    	}
    	public 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;
    	}
    	public static void radixSort(int[] arr, int L, int R, int digit){
    		final int radix = 10;
    		int i = 0,j = 0;
    		// 有多少个数准备多少个辅助空间
    		int[] bucket = new int[R - L + 1];
    		for(int d = 1; d <= digit; d++){
    			int[] count = new int[radix];
    			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);
    				bucket[count[j] - 1] = arr[i];
    				count[j]--;
    			}
    			for( i = L, j = 0; i <= R; i++, j++){
    				arr[i] = bucket[j];
    			}
    		}
    	}
    	// 取数值
    	public static int getDigit(int x, int d){
    		return ((x / ((int)Math.pow(10, d - 1))) % 10);
    	}
    
    • 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

    5. 希尔排序

    // 希尔排序
        public static void shellSort2(int[] arr, int gap){
    		for(int i = gap; i < arr.length; i ++){
    			for(int j =i - gap;j >= 0; j -= gap){
    				if(arr[j] > arr[j + gap])
    					swap(arr, j, j + gap);
    			}
    		}
    		return;
    	}
    	// 部分
    	public static void shellSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		int[] gap = new int[arr.length / 2 + 1];
    		int num = 0;
    		int len = arr.length;
    		while(len > 1){
    			gap[num++] = len / 2;
    			len /= 2;
    		}
    		System.out.println(Arrays.toString(gap));
    		System.out.println(num);
    		for(int i =0; i < num; i++)
    			shellSort2(arr, gap[i]);
    	}
    
    • 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

    6. 快速排序

    public static void quickSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		quickSort(arr, 0, arr.length - 1);
    	}
    
    	public static void quickSort(int[] arr, int L, int R){
    		if(L < R){
    			swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
    			int[] p = partition(arr, L, R);
    			quickSort(arr, L, p[0] - 1);
    			quickSort(arr, p[1] + 1, R);
    		}
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    7. 归并排序

    待写
    
    • 1

    8. 堆排序

    // heapInsert
    	public static void heapInsert(int[] arr, int index){
    		while(arr[index] > arr[(index - 1) / 2]){
    			swap(arr, index, (index - 1) / 2);
    			index = (index - 1) / 2;
    		}
    	}
    	// 某个数在index的位置,能否往下移动
    	public static void heapify(int[] arr, int index, int heapSize){
    		int left = index * 2 + 1;
    		while(left < heapSize){
    			// 两个孩子中,谁值大,下标给largest
    			int largest = left + 1 < heapSize && arr[left + 1] > arr[left]? left + 1 : left;
    			// 父和较大孩子比较
    			largest = arr[largest] > arr[index] ? largest : index;
    			if(largest == index){
    				break;
    			}
    			swap(arr, largest, index);
    			index = largest;
    			left = index * 2 + 1;
    		}
    	}
    	// 堆排序
    	public static void heapSort(int[] arr){
    		if(arr == null || arr.length < 2){
    			return;
    		}
    		// 构造大根堆
    		for(int i = 0; i < arr.length; i++)
    			heapInsert(arr, i);
    		int heapSize = arr.length;
    		swap(arr, 0, --heapSize);
    		while(heapSize > 0){
    			heapify(arr, 0, heapSize);
    			swap(arr, 0, --heapSize);
    		}
    	}
    
    • 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
  • 相关阅读:
    LabVIEW中如何实现任意形状的不规则按键
    C++标准模板(STL)- 类型支持 (数值极限,is_modulo,digits,digits10)
    如何获取 mysql 外键索引的元数据信息?
    C++17 std::filesystem
    Qt+树莓派4B 磁盘、内存、mac地址等系统信息获取
    Kafka使用教程和案例详解
    Java岛屿数量(DFS)
    A40i使用笔记:调用系统自带驱动GT911触摸屏
    哈莫尼斯 手工王国 Harmonis the hand made kingdoms,官方中文,解压即玩,
    芒果改进YOLOv7系列:首发改进特征融合网络BiFPN结构,融合更多有效特征
  • 原文地址:https://blog.csdn.net/weixin_51395608/article/details/137197089