Java 六大排序算法
1. 冒泡排序
public class BubbleSort {
public static void main(String[] args) {
BubbleSort bubbleSort = new BubbleSort();
int[] a = {4,5,6,1,2,3};
System.out.println("排序前：");
for (int i : a) {
System.out.println(i);
}
bubbleSort.bubblesort(a);
System.out.println("排序后：");
for (int i : a) {
System.out.println(i);
}
}
public void bubblesort(int[] a){
int temp;
for (int i = 0; i < a.length; i++){
for (int j = 0; j < a.length - 1 - i; j++){//j从0开始
if (a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
}
2. 选择排序
public class SelectionSort {
public static void main(String[] args) {
int[] a = {4,6,8,7,9,2,10,1};
System.out.println("排序前=================");
for (int i : a) {
System.out.println(i);
}
new SelectionSort().selectionsort(a);
System.out.println("排序前=================");
for (int i : a) {
System.out.println(i);
}
}
public void selectionsort(int[] a){
int temp;
for (int i = 0; i < a.length -1; i++){
int indexMin = i;
for (int j = i; j < a.length; j++){
if (a[indexMin] > a[j]){
indexMin = j; //c
}
}
temp = a[i];
a[i] = a[indexMin];
a[indexMin] = temp;
}
}
}
3. 插入排序
public class InsertionSort {
public static void main(String[] args) {
int[] a = {4,3,2,10,12,1,5,6};
System.out.println("排序前===========");
for (int i : a) {
System.out.println(i);
}
new InsertionSort().insertionsort(a);
System.out.println("排序前===========");
for (int i : a) {
System.out.println(i);
}
}
public void insertionsort(int[] a){
int temp;
for (int i = 1; i < a.length; i++){
for (int j = i; j > 0; j--){
if (a[j-1] > a[j]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
}
4. 希尔排序
public class ShellSort {
public static void main(String[] args) {
int[] a = {9,1,2,5,7,4,8,6,3,5};
System.out.println("排序前===========");
for (int i : a) {
System.out.println(i);
}
new ShellSort().shellsort(a);
System.out.println("排序后===========");
for (int i : a) {
System.out.println(i);
}
}
public void shellsort(int[] a) {
int temp;
//首先确定h的值
int N = a.length;
int h = 0;
while (h < N/2) {
h = h * 2 + 1;
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h; j -= h) {
if (a[j] < a[j - h]) {
temp = a[j];
a[j] = a[j - h];
a[j - h] = temp;
}
}
}
h = h/2;
}
}
}
5. 归并排序
public class MergeSort {
private static int[] assist;
public void sort(int[] a){
assist = new int[a.length];
int lo = 0;
int hi = a.length-1;
sort(a, lo, hi);
}
public void sort(int[] a, int lo, int hi){
if (lo >= hi){ // 注意此处需要判断条件，以终止递归
return;
}
int mid = lo + (hi-lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
public void merge(int[] a, int lo, int mid, int hi){
int i = lo; //该指针指向assist数组
int p1 = lo;
int p2 = mid + 1;
while (p1 <= mid && p2 <= hi){
if (a[p1] < a[p2]){
assist[i++] = a[p1++];
}else {
assist[i++] = a[p2++];
}
}
while (p1 <= mid){
assist[i++] = a[p1++];
}
while (p2 <= hi){
assist[i++] = a[p2++];
}
//复制数组assist给a，注意 index从lo到hi
for (int index = lo; index <= hi; index++) {
a[index] = assist[index];
}
}
public static void main(String[] args) {
int[] a = {2,3,1,5,4,6,7,9,8};
System.out.println("排序前==========");
for (int i : a) {
System.out.print(i+" ");
}
System.out.println(" ");
new MergeSort().sort(a);
System.out.println("排序后==========");
for (int i : a) {
System.out.print(i+" ");
}
}
}
6. 快速排序
public class QuickSort {
public void sort(int[] a){
int lo = 0;
int hi = a.length - 1;
sort(a, lo, hi);
}
public void sort(int[] a, int lo, int hi){
if (lo >= hi){
return;
}
//对a数组中，从lo到hi的元素进行切分
int part = partition(a, lo, hi);
//对左边分组中的元素进行排序
sort(a, lo, part-1);
sort(a, part+1, hi);
}
public int partition(int[] a, int lo, int hi){
int temp;
int key = a[lo]; // 最左边元素做基准
int left = lo;
int right = hi +1; //最右边元素下一个
//进行切分
while (true){
while (key <= a[--right]){//循环停止，证明找到了一个比基准值小的元素
if (right == lo){
break; //已经扫描到最左边了，无需继续扫描
}
}
while (a[++left] <= key){
if (left == hi){
break;
}
}
if (left >= right){
break; //扫描完了所有元素，结束循环
}else {
//交换left和right索引处的元素
temp = a[left];
a[left] = a[right];
a[right] = temp;
}
}
//交换最后right索引处和基准值所在的索引处的值
temp = a[lo];
a[lo] = a[right];
a[right] = temp;
return right; //right就是切分的界限
}
public static void main(String[] args) {
int[] a = {1,4,7,3,2,6,9,8,0};
System.out.println("排序前===========");
for (int i : a) {
System.out.print(i+" ");
}
new QuickSort().sort(a);
System.out.println(" ");
System.out.println("排序后==========");
for (int i : a) {
System.out.print(i+" ");
}
}
}
