package com.test.yjw;
public class Sort {
//冒泡
/**
*
*/
public static void bubbleSort(int a[]) {
int len = a.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for(int t : a){
System.out.println(t);
}
}
//選擇排序
public static void selectSort(int a[]) {
int temp = 0;
int len = a.length;
for (int i = 0; i < len - 1; i++) {
int min = a[i];
int index = i;
for (int j = i + 1; j < len; j++) {
if (min > a[j]) {
min = a[j];
index = j;
}
}
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
for(int t : a){
System.out.println(t);
}
}
// 插入排序{9,5,1,3,7,8,6,2,0,4}
public static void insertSort(int a[]) {
int len = a.length;
for (int i = 1; i < len; i++) {
int temp = a[i];// 待插入的值
int index = i;// 待插入的位置
while (index > 0 && a[index - 1] > temp) {
a[index] = a[index - 1];// 待插入的位置重新賦更大的值
index--;// 位置往前移
}
a[index] = temp;
}
for(int t : a){
System.out.println(t);
}
}
//快速排序
public static void quickSort(int a[], int low, int height) {
if (low < height) {
int result = partition(a, low, height);
quickSort(a, low, result - 1);
quickSort(a, result + 1, height);
}
}
public static int partition(int a[], int low, int height) {
int key = a[low];
while (low < height) {
while (low < height && a[height] >= key)
height--;
a[low] = a[height];
while (low < height && a[low] <= key)
low++;
a[height] = a[low];
}
a[low] = key;
return low;
}
public static void swap(int a[], int i, int j) { // 通過臨時(shí)變量,交換數(shù)據(jù)
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
} // 第一次交換分析
public static void quicksort(int a[], int low, int high) { // 假設(shè)傳入low=0; high=a.length-1;
if (low < high) { // 條件判斷
int pivot, p_pos, i; // 聲明變量
p_pos = low; // p_pos指向low,即位索引為0位置 ;
pivot = a[p_pos]; // 將0位置上的數(shù)值賦給pivot;
for (i = low + 1; i <= high; i++) { // 循環(huán)次數(shù), i=1;
if (a[i]>pivot) { // 1位置的數(shù)與0位置數(shù)作比較: a[1]>a[0]
p_pos++; // 2位與1位比較,3位與2位比較......
swap(a, p_pos, i); // 傳參并調(diào)用swap
}
}
swap(a, low, p_pos); // 將p_pos設(shè)為high再次調(diào)用swap
quicksort(a, low, p_pos - 1); // 遞歸調(diào)用,排序左半?yún)^(qū)
quicksort(a, p_pos + 1, high); // 遞歸調(diào)用,排序右半?yún)^(qū)
}
}
public static void main(String[] args) {
int[] a =new int[]{9,5,1,3,7,8,6,2,0,4};
//Sort.bubbleSort(a);
//Sort.selectSort(a);
//Sort.insertSort(a);
Sort.quickSort(a, 0, a.length-1);
for(int t : a){
System.out.println(t);
}
}
}