java排序算法集

谁践踏了优雅 2022-06-05 07:46 204阅读 0赞

# java中排序算法集 #

java排序算法包括了很多种，包括了插入排序、选择排序、快速排序、归并排序、桶排序、堆排序等等一系列的。

# 一、选择排序的递归与非递归实现 #

首先是非递归实现，代码如下。

/**
    	 * TODO:非递归选择排序算法(每次找出列表中最小元素或者最大元素放到当前列表的开始位置)
    	 * @param noSortList 带排序的列表
    	 * @return Integer[] 排好序的列表
    	 * @author 邪恶小先生
    	 * @time 2017年11月5日
    	 */
    	public static Integer [] selectionSort(Integer [] noSortList){
    		for(int i = 0; i < noSortList.length - 1; i ++){
    			//初始化最开始为最小
    			int minElementIndex = i;
    			for(int j = i + 1; j < noSortList.length; j ++){
    				if(noSortList[j] < noSortList[minElementIndex]){
    					minElementIndex = j;
    				}
    			}
    			//交换元素
    			if(!(minElementIndex == i)){
    				int temp = noSortList[i];
    				noSortList[i] = noSortList[minElementIndex];
    				noSortList[minElementIndex] = temp;
    			}
    		}
    		return noSortList;
    	}

选择排序递归实现，代码如下。

/**
    	 * TODO:递归实现选择选择排序算法，每一次递归都将最小的移动到当前队列第一个元素的位置
    	 * @return Integer[]
    	 * @author 邪恶小先生
    	 * @time 2017年11月9日
    	 */
    	public static Integer [] selectionSortWithRecursion(int nowStartIndex,Integer [] noSortList){
    		if(nowStartIndex >= noSortList.length){
    			return noSortList;
    		}
    		//初始化最小元素为nowStartIndex的地方的元素
    		int minElementIndex = nowStartIndex;
    		int i;
    		//寻找最小元素下标
    		for(i = nowStartIndex; i < noSortList.length; i ++){
    			if(noSortList[i] < noSortList[minElementIndex]){
    				minElementIndex = i;
    			}
    		}
    		//如果下标有变动就执行交换代码块
    		if(minElementIndex!=nowStartIndex){
    			int temp = noSortList[nowStartIndex];
    			noSortList[nowStartIndex] = noSortList[minElementIndex];
    			noSortList[minElementIndex] = temp;
    		}
    		//递归进行
    		return selectionSortWithRecursion(nowStartIndex+1,noSortList);
    	}

# 二、插入排序 #

插入排序非递归实现，代码如下。

/**
    	 * 
    	 * TODO:非递归插入排序算法
    	 * @return Integer[]
    	 * @author 邪恶小先生
    	 * @time 2017年11月9日
    	 */
    	public  static Integer [] insertSort(Integer [] noSortedList){
    		for(int i = 1; i < noSortedList.length; i ++){
    			int j = 0;
    			//找插入的位置
    			while(j < i){
    				if(noSortedList[i] > noSortedList[j]){
    					j++;
    				}
    				else{
    					break;
    				}
    			}
    			//当前被插入的元素所在的位置就正好是要插入，不需要变动
    			if(!(j == i)){
    				//将当前被插入的元素记录下来
    				int temp = noSortedList[i];
    				//移动后面元素的位置
    				for(int m = i; m > j; m -- ){
    					noSortedList[m] = noSortedList[m-1];
    				}
    				//进行插入
    				noSortedList[j] = temp;
    			}
    		}
    		return noSortedList;
    	}

# 三、冒泡排序 #

/**
    	 * TODO:非递归方式的冒泡排序
    	 * @param noSortList 带排序的列表
    	 * @return Integer[] 排好序的列表
    	 * @author 邪恶小先生
    	 * @time 2017年11月5日
    	 */
    	public static Integer [] bubbleSort(Integer [] noSortList){
    		//蛮力，just do it
    		//外层循环用于控制已经排好序的元素不在进行排序
    		for(int i = 0; i < noSortList.length; i ++){
    			//标识当前列表是否已经有序，如果已经有序，就不用在进行排序
    			boolean isInOrder = true;
    			//后面排好序的就不用排序了，所以是noSortList.length - i
    			for(int j = 1; j < noSortList.length - i - 1; j ++){
    				if(noSortList[j] > noSortList[j+1]){
    					//表明列表是无序的
    					isInOrder = false;
    					//swap两个元素
    					int temp = noSortList[j];
    					noSortList[j] = noSortList[j + 1];
    					noSortList[j + 1] = temp;
    				}
    			}
    			//表明列表是有序的，直接退出循环，避免下一次排序
    			if(isInOrder){
    				break;
    			}
    		}
    		return noSortList;
    	}

#    四、快速排序算法 #

package q.experience.exp2;
    
    /**
     * @author 邪恶小先生
     */
    public class QuickSort {
    	/**
    	 * TODO:主调算法
    	 * @return void
    	 * @author 邪恶小先生
    	 * @time 2017年11月21日
    	 */
    	public static void quickSort(Integer [] noSortedList){
    		quickSort(noSortedList,0,noSortedList.length - 1);
    	}
    	
    	/**
    	 * TODO:重载的方法
    	 * @return void
    	 * @author 邪恶小先生
    	 * @time 2017年11月21日
    	 */
    	private static void quickSort(Integer [] partList,int first,int last){
    		if(last > first){
    			int pivotIndex = partition(partList, first, last);
    			//分别对前后部分进行快速排序
    			quickSort(partList,first,pivotIndex - 1);
    			quickSort(partList,pivotIndex + 1, last);
    		}
    	}
    	
    	/**
    	 * 
    	 * TODO:主要的操作函数，进行元素的移动，将比主元小的元素往左边移动，比主元大的元素向右移动，返回主元正确的下标
    	 * @return void
    	 * @author 邪恶小先生
    	 * @time 2017年11月21日
    	 */
    	public static int partition(Integer [] partList,int first, int last){
    		//列表第一个元素作主元
    		int pivot = partList[first];
    		//从左向右扫描的下标开始处
    		int low = first + 1;
    		//从右向左扫描的下标开始处
    		int high = last;
    		
    		//前后扫描整个列表，将比主元大的和小的分别隔开到两端
    		while(high > low){
    			//从左向右扫描第一个大于主元的元素，退出循环的时候要么是越过了界限，要么就是找到了第一个比主元大的元素
    			while(low<=high && partList[low] <= pivot){
    				//向右移动
    				low ++;
    			}
    			
    			//从右向左扫描第一个小于主元的元素，退出循环的时候要么是越过了界限，要么就是找到了第一个比主元大的元素
    			while(low <= high && partList[high] > pivot){
    				//向左移动
    				high --;
    			}
    			
    			//经过上面两个步骤，便找到了第一个比主元大的，和第一个比主元小的元素下标，或者越界
    			//如果没有发生越界，交换两个元素
    			if(high > low){
    				int temp = partList[high];
    				partList[high] = partList[low];
    				partList[low] = temp;
    			}
    		}
    		
    		//现在确定主元pivot的位置
    		while(high > first && partList[high] >= pivot){
    			high --;
    		}
    		
    		//插入主元，返回主元所在的位置
    		if(pivot > partList[high]){
    			partList[first] = partList[high];
    			partList[high] = pivot;
    			return high;
    		}else{
    			return first;
    		}
    	}
    	
    	public static void main(String [] args){
    		Integer [] list = {2,3,2,5,6,1,-2,3,14,12};
    		quickSort(list);
    		System.out.println("排序完成");
    		for(int i = 0; i < list.length; i ++){
    			System.out.println(list[i]);
    		}
    	}
    }