package cn.ffr.sorting;
/**
* 整形排序算法
* @author User
*
*/
public class IntegerSorting {
private static int count = 0;
private IntegerSorting(){};
/**
* 插入排序，O(n^2)
* 将一个记录插入到已排好序的有续表中，从而得到一个新的、记录增一的有序表
* 输出结果：
[No.1]3 6 7 4 1 9 2 5 8 10
[No.2]3 6 7 4 1 9 2 5 8 10
[No.3]3 6 7 4 1 9 2 5 8 10
[No.4]3 4 6 7 1 9 2 5 8 10
[No.5]1 3 4 6 7 9 2 5 8 10
[No.6]1 3 4 6 7 9 2 5 8 10
[No.7]1 2 3 4 6 7 9 5 8 10
[No.8]1 2 3 4 5 6 7 9 8 10
[No.9]1 2 3 4 5 6 7 8 9 10
[No.10]1 2 3 4 5 6 7 8 9 10
*/
public static void insertSort(int[] array){
int temp;
for(int i = 1; i < array.length; i++){
print(array);
temp = array[i];
if(temp < array[i-1]){
int j = i - 1;
for(; j >= 0; j--){
if(array[j] > temp){
array[j+1] = array[j];//向后移动
}else{
array[j+1] = temp;
break;
}
}
if(j < 0){
array[j+1] = temp;//最小的，插入到最前面
}
}
}
}
/**
* 希尔排序
* 先将整个待排序的记录分割成若个子序列分别进行插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序
* 数据以增量的方式向前移动，提高插入排序的效率
* 输出结果：
[No.1]3 6 7 4 1 9 2 5 8 10
[No.2]3 6 7 4 1 9 2 5 8 10
[No.3]3 1 7 4 6 9 2 5 8 10
[No.4]3 1 7 4 6 9 2 5 8 10
[No.5]2 1 7 3 6 9 4 5 8 10
[No.6]2 1 7 3 5 9 4 6 8 10
[No.7]2 1 7 3 5 8 4 6 9 10
[No.8]2 1 7 3 5 8 4 6 9 10
[No.9]1 2 7 3 5 8 4 6 9 10
[No.10]1 2 7 3 5 8 4 6 9 10
[No.11]1 2 3 7 5 8 4 6 9 10
[No.12]1 2 3 5 7 8 4 6 9 10
[No.13]1 2 3 5 7 8 4 6 9 10
[No.14]1 2 3 4 5 7 8 6 9 10
[No.15]1 2 3 4 5 6 7 8 9 10
[No.16]1 2 3 4 5 6 7 8 9 10
[No.17]1 2 3 4 5 6 7 8 9 10
*/
public static void shellSort(int[] array){
int[] steps = {3, 1};
for(int step : steps){
_shellSort(array, step);//步长分别为3、1
}
}
/**
* 希尔排序的一次排序方法
* @param array
* @param step
*/
private static void _shellSort(int[] array, int step){
int temp;
for(int i = step; i < array.length; i++){
print(array);
temp = array[i];
if(temp < array[i-step]){
int j = i - step;
for(; j >= 0; j = j - step){
if(array[j] > temp){
array[j+step] = array[j];//向后移动
}else{
array[j+step] = temp;
break;
}
}
if(j < 0){
array[j+step] = temp;//最小的，插入到最前面
}
}
}
}
/**
* 冒泡排序，O(n^2)
* 一次排序后将最大的关键字沉入底部
[No.1]3 6 7 4 1 9 2 5 8 10
[No.2]3 6 4 1 7 2 5 8 9 10
[No.3]3 4 1 6 2 5 7 8 9 10
[No.4]3 1 4 2 5 6 7 8 9 10
[No.5]1 3 2 4 5 6 7 8 9 10
[No.6]1 2 3 4 5 6 7 8 9 10
[No.7]1 2 3 4 5 6 7 8 9 10
[No.8]1 2 3 4 5 6 7 8 9 10
[No.9]1 2 3 4 5 6 7 8 9 10
[No.10]1 2 3 4 5 6 7 8 9 10
*/
public static void bubbleSort(int[] array){
for(int i = 0; i < array.length - 1; i++){//最有一次比较没有意义，所以条件为：i<array.length-1
print(array);
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j + 1]){
swap(array, j, j+1);
}
}
}
}
/**
* 快速排序,O(nlogn)
* 对冒泡排序的改进，先整体有序，在局部有序
* 输出结果：
[No.1]3 6 7 4 1 9 2 5 8 10
[No.2]2 1 3 4 7 9 6 5 8 10
[No.3]1 2 3 4 7 9 6 5 8 10
[No.4]1 2 3 4 7 9 6 5 8 10
[No.5]1 2 3 4 7 9 6 5 8 10
[No.6]1 2 3 4 7 9 6 5 8 10
[No.7]1 2 3 4 7 9 6 5 8 10
[No.8]1 2 3 4 5 6 7 9 8 10
[No.9]1 2 3 4 5 6 7 9 8 10
[No.10]1 2 3 4 5 6 7 9 8 10
[No.11]1 2 3 4 5 6 7 9 8 10
[No.12]1 2 3 4 5 6 7 8 9 10
[No.13]1 2 3 4 5 6 7 8 9 10
[No.14]1 2 3 4 5 6 7 8 9 10
*/
public static void quickSort(int[] array, int low, int high){
print(array);
if(low < high){
int mid = _quickSort(array, low, high);
quickSort(array, low, mid-1);
quickSort(array, mid+1, high);
}
}
/**
* 一次快速排序
*/
private static int _quickSort(int[] array, int low, int high){
int index = array[low];
while(low < high){
while(low < high && array[high] > index) high--;
array[low] = array[high];
while(low < high && array[low] < index) low++;
array[high] = array[low];
}
array[low] = array[high] = index;
return low;
}
/**
* 选择排序，采用关键字的比较，O(n^2)
* 在每趟n-i+1个记录中，选择最小的记录作为有序序列的第i个记录
* 输出结果：
[No.1]3 6 7 4 1 9 2 5 8 10
[No.2]1 6 7 4 3 9 2 5 8 10
[No.3]1 2 7 6 4 9 3 5 8 10
[No.4]1 2 3 7 6 9 4 5 8 10
[No.5]1 2 3 4 7 9 6 5 8 10
[No.6]1 2 3 4 5 9 7 6 8 10
[No.7]1 2 3 4 5 6 9 7 8 10
[No.8]1 2 3 4 5 6 7 9 8 10
[No.9]1 2 3 4 5 6 7 8 9 10
[No.10]1 2 3 4 5 6 7 8 9 10
*/
public static void selectSort(int[] array){
for(int i = 0; i < array.length - 1; i++){
print(array);
for(int j = i+1; j < array.length; j++){
if(array[j] < array[i]){
swap(array, i, j);
}
}
}
}
private static void print(int[] array){
count++;
System.out.print("[No."+count+"]");
for(int a :array){
System.out.print(a+" ");
}
System.out.println();
}
private static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {3, 6, 7 ,4, 1, 9, 2, 5, 8, 10};
// IntegerSorting.insertSort(array);
// IntegerSorting.shellSort(array);
// IntegerSorting.bubbleSort(array);
// IntegerSorting.quickSort(array, 0, array.length - 1);
IntegerSorting.selectSort(array);
print(array);
}
}