九大排序算法之代码实现

一：冒泡排序法 Java代码： public class bubble_sort { public static void main(String args[]){ int[] number = {23,12,48,17,36}; bubble_sort(number);

for(int i=0;i<number.length;i++){ System.out.println(number[i]); } } public static void bubble_sort(int[] arr){ int temp; for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } }

二：简单选择排序 Java代码 package rankDemo;

public class SimpleSort {

public static void main(String[] args) { int[] number = {23,12,47,18,36}; SimpleSort(number); for(int k=0;k<number.length;k++){ System.out.println(number[k]); } } private static void SimpleSort(int[] number) { int temp,min = 0; for(int i=0;i<number.length-1;i++){ temp = number[i]; for(int j=i+1;j<number.length;j++){ if(number[j]<temp){ //找到最小的值 记录下最小值得索引 min = j; temp = number[j]; } } if(min!=i){ //交换顺序 temp = number[min]; number[min] = number[i]; number[i] = temp; } } }

}

三：希尔排序 package rankDemo; public class shellSort { public static void main(String[] args) { int[] number = {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};

shellSort(number); for(int k=0;k<number.length;k++){ System.out.println(number[k]); } } public static void shellSort(int[] a) { int gap = 1, i, j, len = a.length; int temp;//插入排序交换值的暂存 //确定初始步长 while (gap < len / 3){ gap = gap * 3 + 1; } for (; gap > 0; gap /= 3){//循环遍历步长，最后必为1 for (i = gap; i < len; i++) {//每一列依次向前做插入排序 temp = a[i]; //每一列中在a[i]上面且比a[i]大的元素依次向下移动 for (j = i - gap; j >= 0 && a[j] > temp; j -= gap){ a[j + gap] = a[j]; } //a[i]填补空白，完成一列中的依次插入排序 a[j + gap] = temp; } } }

}

四：归并排序 Java代码 package rankDemo;

public class merge_sort {

public static void main(String[] args) { int [] arr ={6,5,3,1,8,7,2,4}; merge_sort(arr); for(int i : arr){ System.out.println(i); } }

public static void merge_sort(int[] arr) { int len = arr.length; //用于合并的临时数组 int[] result = new int[len]; int block, start;

//两两合并后块大小变大两倍 (注意最后一次block等于len) for(block = 1; block <=len ; block *= 2) { //把整个数组分成很多个块，每次合并处理两个块 for(start = 0; start <len; start += 2 * block) { int low = start; int mid = (start + block) < len ? (start + block) : len; int high = (start + 2 * block) < len ? (start + 2 * block) : len; //两个块的起始下标及结束下标 int start1 = low, end1 = mid; int start2 = mid, end2 = high; //开始对两个block进行归并排序 while (start1 < end1 && start2 < end2) { result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; } while(start1 < end1) { result[low++] = arr[start1++]; } while(start2 < end2) { result[low++] = arr[start2++]; } } //每次归并后把结果result存入arr中，以便进行下次归并 int[] temp = arr; arr = result; result = temp; } }

}

五：快速排序 Java代码： package rankDemo;

public class quickSort { public static void main(String[] args) { int [] arr = {8,1,0,4,6,2,7,9,5,3}; quickSort(arr,0,arr.length-1); for(int i :arr){ System.out.println(i); } } public static void quickSort(int[]arr,int low,int high){ if (low < high) { int middle = getMiddle(arr, low, high); quickSort(arr, low, middle - 1); quickSort(arr, middle + 1, high); } } public static int getMiddle(int[] list, int low, int high) { int tmp = list[low]; while (low < high) { while (low < high && list[high] >= tmp) { high–; } list[low] = list[high]; while (low < high && list[low] <= tmp) { low++; } list[high] = list[low]; } list[low] = tmp; return low; } }

六：堆排序 Java代码： package rankDemo;

public class HeapSort { private static int[] sort = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11}; public static void main(String[] args) { buildMaxHeapify(sort); heapSort(sort); print(sort); } private static void buildMaxHeapify(int[] data){ //没有子节点的才需要创建最大堆，从最后一个的父节点开始 int startIndex = getParentIndex(data.length - 1); //从尾端开始创建最大堆，每次都是正确的堆 for (int i = startIndex; i >= 0; i--) { maxHeapify(data, data.length, i); } } /** * 创建最大堆 * @param data * @param heapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了 * @param index当前需要创建最大堆的位置 */ private static void maxHeapify(int[] data, int heapSize, int index){ // 当前点与左右子节点比较 int left = getChildLeftIndex(index); int right = getChildRightIndex(index); int largest = index; if (left < heapSize && data[index] < data[left]) { largest = left; } if (right < heapSize && data[largest] < data[right]) { largest = right; } //得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整 if (largest != index) { int temp = data[index]; data[index] = data[largest]; data[largest] = temp; maxHeapify(data, heapSize, largest); } } /** * 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的 * @param data */ private static void heapSort(int[] data) { //末尾与头交换，交换后调整最大堆 for (int i = data.length - 1; i > 0; i--) { int temp = data[0]; data[0] = data[i]; data[i] = temp; maxHeapify(data, i, 0); } } /** * 父节点位置 * @param current * @return */ private static int getParentIndex(int current){ return (current - 1) >> 1; } /** * 左子节点position注意括号，加法优先级更高 * @param current * @return */ private static int getChildLeftIndex(int current){ return (current << 1) + 1; } /** * 右子节点position * @param current * @return */ private static int getChildRightIndex(int current){ return (current << 1) + 2; } private static void print(int[] data){ for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " |"); } } }

七：桶排序 Java代码 package rankDemo;

import java.util.ArrayList; import java.util.Iterator;

public class BucketSort { /** * 对arr进行桶排序，排序结果仍放在arr中 */ public static void bucketSort(double arr[]){ //-------------------------------------------------分桶----------------------------------------------- int n = arr.length; //存放桶的链表 ArrayList bucketList[] = new ArrayList [n]; //每个桶是一个list，存放此桶的元素 for(int i =0;i<n;i++){ //下取等 int temp = (int) Math.floor(n*arr[i]); //若不存在该桶，就新建一个桶并加入到桶链表中 if(null==bucketList[temp]) bucketList[temp] = new ArrayList(); //把当前元素加入到对应桶中 bucketList[temp].add(arr[i]); } //-------------------------------------------------桶内排序----------------------------------------------- //对每个桶中的数进行插入排序 for(int i = 0;i<n;i++){ if(null!=bucketList[i]) insert(bucketList[i]); } //-------------------------------------------------合并桶内数据----------------------------------------------- //把各个桶的排序结果合并 int count = 0; for(int i = 0;i<n;i++){ if(null!=bucketList[i]){ Iterator iter = bucketList[i].iterator(); while(iter.hasNext()){ Double d = (Double)iter.next(); arr[count] = d; count++; } } } } /** * 用插入排序对每个桶进行排序 * 从小到大排序 */ public static void insert(ArrayList list){ if(list.size()>1){ for(int i =1;i<list.size();i++){ if((Double)list.get(i)<(Double)list.get(i-1)){ double temp = (Double) list.get(i); int j = i-1; for(;j>=0&&((Double)list.get(j)>(Double)list.get(j+1));j--) list.set(j+1, list.get(j)); //后移 list.set(j+1, temp); } } } } }

测试代码： public static void main(String[] args) { double arr [] ={0.21,0.23,0.76,0.12,0.89}; BucketSort.bucketSort(arr); for(double a:arr){ System.out.println(a); } }

八：基数排序 Java代码 package rankDemo;

import java.awt.List; import java.util.ArrayList;

public class radixSort { public static void main(String[] args) {

int[] array = {278,109,63,930,589,184,505,269,8,83}; radixSort(array); for(double a : array){ System.out.println(a); } }

public static void radixSort(int[] array){

//------------------------------------------确定排序的趟数---------------------------------- int max=array[0]; for(int i=1;i<array.length;i++){ if(array[i]>max){ max=array[i]; } } int time=0; while(max>0){ max/=10; time++; } //----------------------------------------初始化10个链表用户分配时暂存------------------------------- List<List<Integer>> list=new ArrayList<List<Integer>>(); for(int i=0;i<10;i++){ List<Integer> item=new ArrayList<Integer>(); list.add(item); } //-----------------------------------------进行time次分配和收集------------------------------------- for(int i=0;i<time;i++){ //分配元素; for(int j=0;j<array.length;j++){ int index = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i); list.get(index).add(array[j]); } //收集元素; int count=0; for(int k=0;k<10;k++){ if(list.get(k).size()>0){ for(int a : list.get(k)){ array[count]=a; count++; } //清除数据，以便下次收集 list.get(k).clear(); } } } }

}

九：插入排序 Java代码 package rankDemo; public class insertSort{ public static void main(String[] args) { int[] number = {23,12,47,18,36};

insertSort(number); for(int k=0;k<number.length;k++){ System.out.println(number[k]); } }

public static void insertSort(int a[]){ int j; //当前要插入值的位置 int preJ; //依次指向j前的位置 int key; //后移时来暂存要插入的值

//从数组的第二个位置开始遍历值 for(j=1;j<a.length;j++){ key=a[j]; preJ=j-1; //a[preJ]比当前值大时，a[preJ]后移一位 while(preJ>=0 && a[preJ]>key){ a[preJ+1]=a[preJ]; //将a[preJ]值后移 //这里注意: a[preJ+1]=a[j]=key,把插入值已经存在了 key中 //等于说, 留出来一个空白位置来实现依次后移（不会造成数据丢失问题） preJ--; //preJ前移 } //找到要插入的位置或已遍历完成（(preJ=0） a[preJ+1]=key; //将当前值插入 空白位置 } }

}