1.快速排序
package dataStructure;import java.util.Arrays;public class QuickSort {private static int adjust(int[] a, int l, int r) {int x = a[l];while (l < r) {while (l<r && a[r] >= x){r--;}if (l < r){a[l]=a[r];l++;}while (l<r && a[l] < x){l++;}if(l<r){a[r]=a[l];r--;}}a[l]=x;return l;}private static void quickSort(int[] a, int l, int r) {if (l < r) {int mid = adjust(a, l, r);quickSort(a, l, mid-1);quickSort(a, mid+1,r);}}public static void main(String[] args) {int[] a = {5, 9, 8, 9, 1, -1};quickSort(a, 0, a.length - 1);System.out.println(Arrays.toString(a));}}
2.冒泡排序
package dataStructure;import java.util.Arrays;public class BubbleSort {private static void bubbleSort(int[] a, int n){for (int i = 0; i < n-1;i++){for (int j = 0; j < n-1-i; j++){if(a[j] > a[j+1]){int x = a[j];a[j] = a[j+1];a[j+1] = x;}}}}public static void main(String[] args) {int[] a = {5, 9, 8, 9, 1, -1};bubbleSort(a, a.length);System.out.println(Arrays.toString(a));}
}
3.归并排序
package dataStructure;import java.util.Arrays;public class MergeSort {private static void adjust(int[] a,int l,int mid,int r){int [] temp = new int [r-l+1];int i = l, j = mid+1;int cnt = 0;while (i<=mid && j<=r){if(a[i]<=a[j]){temp[cnt++]=a[i++];}else {temp[cnt++]=a[j++];}}while (i<=mid){temp[cnt++]=a[i++];}while (j<=r){temp[cnt++]=a[j++];}for (int k = 0; k < cnt;k++){a[l+k] = temp[k];}}private static void mergeSort(int[] a, int l, int r){if(l<r){int mid = (l+r) >> 1;mergeSort(a, l, mid);mergeSort(a, mid+1, r);adjust(a,l,mid,r);}}public static void main(String[] args) {int[] a = {5, 9, 8, 9, 1, -1};mergeSort(a, 0, a.length-1);System.out.println(Arrays.toString(a));}
}
4.堆排序
package dataStructure;import java.util.Arrays;public class HeapSort {private static void swap(int[] a,int x,int y){int temp = a[x];a[x]=a[y];a[y]=temp;}private static void max_heap(int[] a,int start,int end){int fa = start;int son = start*2+1;while (son<=end){if(son+1 < end && a[son] < a[son+1]){son++;}if(a[fa]>a[son]){return;}else{swap(a,fa,son);fa = son;son = son*2+1;}}}private static void heapSort(int[] a,int len){//数组从0开始，所以最后一个父亲节点的下标为len/2-1for (int i = len/2-1; i >= 0;i--){max_heap(a,i,len-1);}for (int i = len-1; i > 0;i--){swap(a,0,i);max_heap(a,0, i-1);}}public static void main(String[] args) {int[] a = {5, 9, 8, 9, 1, -1};heapSort(a, a.length);System.out.println(Arrays.toString(a));}
}
5.插入排序
package dataStructure;import java.util.Arrays;public class InsertionSort {private static void insertionSort(int[] a,int n){for (int i = 1; i < n;i++){int x = a[i];int j = i-1;while (j>=0 && x<a[j]){a[j+1]=a[j];j--;}a[j+1]=x;}}public static void main(String[] args) {int[] a = {5, 9, 8, 9, 1, -1};insertionSort(a,a.length);System.out.println(Arrays.toString(a));}
}