常见的排序算法（Java实现）：冒泡、插入、选择、快速排序
/** * 常见的排序算法实现 * 1.冒泡排序 * 2.插入排序 * 3.选择排序 * 4.快速排序 * @author 健身小码哥 * */ public class SortManager { /** * 冒泡排序 * 原理：每次遍历，将剩余子数组中的最大值移动到子数组的尾端 * @param array */ public void bubbleSort(int array[]) { if(array == null || array.length < 2) { return; } int length = array.length; for(int i = 0 ; i < array.length ; i++) { for(int j = 0 ; j < length - i -1; j++) { //将较大的元素向后移动 if(array[j] > array[j+1]) { int temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } } } /** * 插入排序 * @param array */ public void insertionSort(int array[]) { if(array == null || array.length < 2) { return; } for(int i = 1 ; i < array.length ; i++) { for(int j = i ; j > 0 ; j--) { if(array[j] < array[j-1]) { swap(array,j,j-1); } } } } /** * 选择排序 * @param array */ public void selectionSort(int array[]) { if(array == null || array.length < 2) { return; } for(int i = 0 ; i < array.length ; i++) { int maxPos = 0; for(int j = 0 ; j < array.length -i; j++) { maxPos = array[maxPos] > array[j] ? maxPos : j; } swap(array , maxPos , array.length - i - 1); } } /** * 快速排序，选取最后一个元素作为参考，输出数组的非递减序列 * @param array 待排序的数组 * @param start 要排序数组的开始位置 * @param end 要排序数组的结束位置 */ public void quickSort(int array[] , int start , int end) { if(array == null || array.length < 2 || start >= end) { return; } //选取最后一个元素作为参考 int flag = array[end]; //记录大于flag的第一个元素位置 int i = start-1; //标识当前遍历的位置 int j = start ; while(j < end) { //当元素小于flag时，与++i进行交换 if( array[j] < flag) { i++; swap(array,i,j); } j++; } //将flag交换到合适的位置 int mid = i + 1; swap(array,mid,end); //对左右子数组进行递归排序 quickSort(array,start,mid -1); quickSort(array,mid + 1,end); } /** * 快速排序，选取最后一个元素作为关键值，输出数组的非递减序列 * @param array 待排序的数组 * @param start 要排序数组的开始位置 * @param end 要排序数组的结束位置 */ public void quickSort2(int array[] , int start , int end) { if(array == null || array.length < 2 || start >= end) { return; } int flag = array[end]; //1.从左向右遍历，寻找比flag大的元素left //2.从右向左遍历，寻找比flag小的元素right //3.交换元素位置，直到left >= right ， 将参考值交换到合适的位置 int left = start; int right = end; while(left < right) { if(array[left] <= flag) { left++; }else if(array[right] >= flag) { right--; }else { swap(array,left,right); } } //将flag交换到合适的位置 swap(array,left,end); //对左右子数组进行递归排序 quickSort2(array,start,left -1); quickSort2(array,left + 1,end); } /** * 交换数组中两元素的位置 * @param array * @param x * @param y */ private void swap(int array[] , int x , int y) { int temp = array[x]; array[x] = array[y]; array[y] = temp; } }
