排序算法（JAVA实现）

package com.saigu; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub try{ int a[] = {21,25,49,25,16,8}; //quickSort(a,0,a.length - 1); //insertSort(a,0,a.length - 1); mergeSort(a,0,a.length - 1); for(int i = 0; i < a.length; i++) System.out.println(a[i]); }catch(Exception e){ System.out.println(e); } } /**快速排序 * 时间复杂度O(nlogn),理想空间复杂度O(logn) * @param a:待排序数组 * @param left * @param right */ public static void quickSort(int a[], int left, int right){ if(left < right){ //int pivotPos = changePos(a,left,right); //changePos int pivotPos = left; int pivot = a[left]; for(int i = left + 1; i <= right; i++){ if(a[i] < pivot){ pivotPos++; int tmp = a[i]; a[i] = a[pivotPos]; a[pivotPos] = tmp; } } a[left] = a[pivotPos]; a[pivotPos] = pivot; quickSort(a,left,pivotPos - 1); quickSort(a,pivotPos + 1,right); } } /**插入排序 * 时间复杂度O(n^2) * @param a * @param left * @param right */ public static void insertSort(int a[], int left, int right){ for(int i = left + 1; i <= right; i++){ if(a[i] < a[i - 1]){ int temp = a[i]; int j = i - 1; do{ a[j + 1] = a[j]; j--; }while(j >= left && a[j] > temp); a[j + 1] = temp; } } } <pre name="code" class="java">/**堆排序 * * @param num * @param begin * @param end */ public static void makeMaxHeap(int[] num, int begin, int end){ int i = begin; int j = 2 * i + 1; //左节点 int tmp = num[i]; while(j <= end){ if(j < end && num[j] < num[j + 1]) j++;//取左右节点中较大的一个 if(tmp > num[j]) break; else{ num[i] = num[j]; i = j; j = 2 * i + 1; } } num[i] = tmp; } public static void heapSort(int[] num){ //构建最大堆 for(int i = (num.length - 1 - 1)/2; i >= 0; i--){ makeMaxHeap(num,i,num.length - 1); } //排序 for(int i = num.length - 1; i >= 0; i--){ int tmp = num[i]; num[i] = num[0]; num[0] = tmp; makeMaxHeap(num,0,i - 1); } } <pre name="code" class="java">/**归并排序 * * 时间复杂度O(nlogn) * * 稳定排序 * @param a * * @param left * * @param right */ public static void mergeSort(int a[], int left, int right){ int mid = (left + right)/2; if(left < right){ mergeSort(a,left,mid); mergeSort(a,mid + 1,right); merge(a,left,mid,right); } } public static void merge(int a[], int left, int mid, int right){ int[] tmp = new int[right - left + 1]; int i = left;//左指针 int j = mid + 1; //右指针 int k = 0;//合并数组 while(i <= mid && j <= right){ if(a[i] < a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } //把左边剩余数组放进去 while(i <= mid){ tmp[k++] = a[i++]; } //把右边剩余数组放进去 while(j <= right){ tmp[k++] = a[j++]; } //赋值 for(int p = 0; p < right - left + 1; p++) a[p + left] = tmp[p]; //注意这里是a[p + left]; }