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) { // 通过临时变量,交换数据
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
} // 第一次交换分析
public static void quicksort(int a[], int low, int high) { // 假设传入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位置上的数值赋给pivot;
for (i = low + 1; i <= high; i++) { // 循环次数, i=1;
if (a[i]>pivot) { // 1位置的数与0位置数作比较: a[1]>a[0]
p_pos++; // 2位与1位比较,3位与2位比较......
swap(a, p_pos, i); // 传参并调用swap
}
}
swap(a, low, p_pos); // 将p_pos设为high再次调用swap
quicksort(a, low, p_pos - 1); // 递归调用,排序左半区
quicksort(a, p_pos + 1, high); // 递归调用,排序右半区
}
}
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);
}
}
}