【2019.07.04】java 数组选择排序，二分法查找

港控/mmm° 2021-12-15 07:59 170阅读 0赞

# 数组选择排序 #

*  选择数列中的最小数，然后将它和数列中的第一个数字互换

/** * 数组选择排序 * @param list 待排序的数组 * @return */
    	private static double[] selectionSort(double[] list) { 
    		for (int i = 0; i < list.length; i++) { 
    			double currentMin = list[i];
    			int currentMinIndex = i;
    		
    			for (int j = i + 1; j < list.length; j++) { 
    				if (currentMin > list[j]) { 
    					currentMin = list[j];
    					currentMinIndex = j;
    				}
    			}
    			
    			if (currentMinIndex != i) { 
    				list[currentMinIndex] = list[i];
    				list[i] = currentMin;
    			}
    		}
    		return list;
    	}

# 数组二分法查找 #

*  前提：数组中的元素必须已经按照从大到小或从小到大排序好

/** * 二分查找 * @param list 数组 * @param key 待查找元素 * @return 待查找元素的下标/-1 */
    	private static int binarySearch(double[] list, double key) { 
    		int low = 0;
    		int high = list.length -1;
    		
    		while (high >= low) { 
    			int mid = (low + high) / 2;
    			if (key < list[mid])
    				high = mid - 1;
    			else if(key == list[mid])
    				return mid;
    			else
    				low = mid + 1;
    		}
    		
    		return -1;
    	}

# 测试类 #

package com.ybs.practice;
    
    import javax.sound.midi.MidiChannel;
    
    /** * @Description 类描述：数组选择排序 * @ClassName 类名称： * @author yb.w * @version 创建时间：2019年7月4日 下午5:23:33 */
    public class SelectionSort { 
    	public static void main(String[] args) { 
    		
    		double[] list = { 1, -3, 9 , 4.5, 6.6, 5.7, -4.5};
    		double[] result = selectionSort(list);
    		
    		int binarySearch = binarySearch(result, 6.6);
    		System.out.println(binarySearch);
    	}
    	
    	/** * 数组选择排序 * @param list 待排序的数组 * @return */
    	private static double[] selectionSort(double[] list) { 
    		for (int i = 0; i < list.length; i++) { 
    			double currentMin = list[i];
    			int currentMinIndex = i;
    		
    			for (int j = i + 1; j < list.length; j++) { 
    				if (currentMin > list[j]) { 
    					currentMin = list[j];
    					currentMinIndex = j;
    				}
    			}
    			
    			if (currentMinIndex != i) { 
    				list[currentMinIndex] = list[i];
    				list[i] = currentMin;
    			}
    		}
    		return list;
    	}
    	
    	/** * 二分查找 * @param list 数组 * @param key 待查找元素 * @return 待查找元素的下标/-1 */
    	private static int binarySearch(double[] list, double key) { 
    		int low = 0;
    		int high = list.length -1;
    		
    		while (high >= low) { 
    			int mid = (low + high) / 2;
    			if (key < list[mid])
    				high = mid - 1;
    			else if(key == list[mid])
    				return mid;
    			else
    				low = mid + 1;
    		}
    		
    		return -1;
    	}
    }