算法复习（一）

Bertha 。 2024-04-18 21:20 52阅读 0赞

1、冒泡

/*
    	 * 冒泡排序
    	 */
    	public static  int[] sort2(int [] arr){
    		for(int i = 0;i < arr.length -1;i++){  //选出一个最大值/最小值需要进行多少轮筛选
    			for (int j = 0; j < arr.length - i -1; j++) {//每轮筛选需要一次互换
    				if(arr[j] > arr[j+1]){
    					int temp = arr[j+1];
    					arr[j+1] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		return arr;
    	}

2、选择排序

/*
    	 * 选择排序
    	 */
    	public static  int[] sort(int [] arr){
    		for(int i =0;i<arr.length-1;i++){
    			int index = i;//假设最小的是第一个
    			for (int j = i; j < arr.length; j++) {
    				if(arr[j] < arr[index]){//有比设定值还小的，则将最小值的索引进行更新
    					index = j;
    				}
    			}
    			/*
    			 * 将实际最小值与设定最小值进行位置互换
    			 */
    			int temp = arr[index];
    			arr[index] = arr[i];
    			arr[i] = temp;
    		}
    		return arr;
    	}

3、插入排序

流水:
    /*
    	 * 插入排序
    	 */
    	public static int[] sort3(int[] arr){
    		for (int i = 1; i < arr.length; i++) {
    			int num = arr[i];  //定义待插入的数
    			int index = i-1;//定义待插入数的下标,先假定插入位置为前一个位置，通过while循环依次向前推，最小的话则为第一个元素
    			while (index >= 0 && num <arr[index]) {
    				arr[index+1] =arr[index];
    				index--;
    			}
    			arr[index+1] = num;
    		}
    		return arr;
    	}

4、

/*
      * 希尔排序
      */
     public static int[] sort4(int[] arr){
      for (int gap = arr.length / 2; gap > 0; gap /= 2) {
       // 对数组元素进行分组
       for (int i = gap; i < arr.length; i++) { //考虑奇数情况，所以取后半部分，作为分组数目
        // 遍历各组中的元素
        for (int j = i - gap; j >= 0; j -= gap) { //从数组开始位置遍历
         // 交换元素
         if (arr[j] > arr[j + gap]) {
          int temp = arr[j];
          arr[j] = arr[j + gap];
          arr[j + gap] = temp;
         }
        }
       }
      }
      return arr;
     }