/**
* SimpleArraySortUtils.java
* @author 卢富毓
*
*/
public class SimpleArraySortUtils {
/*
* 冒泡排序算法的运作如下：（从后往前）
* 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
* 针对所有的元素重复以上的步骤，除了最后一个。
* 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
* 效率O(N^2)
*/
public void BubbleSort(int[] arr){
//升序 优化：相邻两个数字比较
int len = arr.length;
for(int i=0; i<len - 1; i++){
for(int j=0; j<len-i-1; j++){
if(arr[j+1] < arr[j]){ //比较交换
ArrayUtils.swap(arr, j+1, j);
}
}
}
ArrayUtils.diplay(arr);
}
public void BubbleSort2(int[] arr) {
int i = arr.length, j;
int temp;
while (i > 0) {
for (j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i--;
}
}
/*
* 选择排序规则：
* 初始化：arr[1...n]
* 第一趟一arr[0]为标记，min=0;在n-1中寻找是否有比arr[0]还小的数值a[m],使得 min = m;
* 遍历n-1个数之后得到arr[min]为最小
* 对arr[0]与arr[min]交换
* 第二趟arr[1]开始重复第一趟。
*
*/
//选择排序
public void SelectSort(int[] arr) {
int len = arr.length;
for(int i=0; i<len-1; i++ ){
int k = i;
for(int j=i+1; j<len; j++){
if(arr[j] < arr[k]){
k=j;
}
}
if(k != i){
ArrayUtils.swap(arr, i, k);
}
}
ArrayUtils.diplay(arr);
}
/*
* 插入排序
* 初始化：arr[1...n]
* 第一趟：找到未排序的元素的下标i(默认0...i-1都已经排序)
* 在0...i-1中找到k arr[k-1]<arr[i]<arr[k]
* 将k...i-1的元素右移一位，将arr[i]插入。
* 第二趟：重复第一趟
*
* 图形表示
* 第一趟：
* 1 2 3 5 || 4 9 8 7 6
* 1 2 3 5 || 4 9 8 7 6
* 1 2 3 4 5 || 9 8 7 6
* 第二趟
* 1 2 3 4 5 || 9 8 7 6
* 1 2 3 4 5 9 || 8 7 6
* …… ……
* 1 2 3 4 5 6 7 8 9
*/
public static void InsertSort(int[] arr){
int len = arr.length;
for(int i=1; i<len; i++){
int temp = arr[i];//记录下当前无序的元素
int j = i; //记下当前元素的下标
while(j > 0 && arr[j-1] >= temp ){
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
ArrayUtils.diplay(arr);
}
//希尔排序是在插入排序的基础上改进的
//由于插入排序中复制数据的次数太多
//希尔排序在最坏情况和平均情况下的效率差不多。比起直接插入排序效率快
public static void ShellSort(int[] arr){
//knuth序列
int h = 1;
while(h <= arr.length/3){
h = h*3 +1;
}
while(h>0){
for(int i=h; i<arr.length; i++){
int temp = arr[i];
int j = i;
while(j > h-1 && arr[j-h] >= temp){
arr[j] = arr[j-h];
j = j-h;
}
arr[j] = temp;
}
h = (h-1)/3; //knuth序列减
}
ArrayUtils.diplay(arr);
}
}
/******************************************************************************/
package cn.fly.simplesort;
/**
* ArrayUtils.java
* @author 卢富毓
*
*/
import java.util.Scanner;
public class ArrayUtils {
public static int[] init(){
int len; //数组大小
int[] arr;//元素数组
Scanner in = new Scanner(System.in);
System.out.print("请输入数组大小 len = ");
len = in.nextInt();
arr = new int[len];
System.out.print("请输入数据元素：");
for(int i=0; i<len; i++){
arr[i] = in.nextInt();
}
in.close();
return arr;
}
public static void swap(int[] arr, int i, int k){
arr[i] = arr[i] + arr[k];
arr[k] = arr[i] - arr[k];
arr[i] = arr[i] - arr[k];
}
public static void diplay(int[] arr){
for(int l=0; l<arr.length; l++){
System.out.print(arr[l] + " ");
}
System.out.println();
}
}
