排序算法及java实现

import java.util.*;

public class Test {
private static int[] array;

public static void main(String[] args) {
/*
System.out.println("Please enter 10 numbers seperated by space");
Scanner sc = new Scanner(System.in);

for (int i = 0; i < array.length; i++) {
if (sc.hasNext()) {
array[i] = sc.nextInt();
}
}*/

array = new int[]{23,52,11,21,99,1,6,3,91,33,100,23,52,11,21,99,1,6,3,91,33,100,92,85,399,12,1};

//bubbleSort(array);

//selectSort(array);

//insertSort(array);

//shellSort(array);

//directInsertSort(array);

//directInsertSortGuard(array);

mergeSort(array, 0, array.length-1);

//quickSort(array, 0, array.length-1);

for (int i: array) {

System.out.println(i);
}
}

/**
冒泡排序

两两比较，小的往后移动。多次循环，直到有序为止。
比较次数C，移动次数M
最好情况：正序的
比较次数C= n-1
移动次数M= 0
最坏情况：倒序
比较次数C= n*(n-1)/2   第一次比较n次，之后比较n-i次
移动次数M= 3n*(n-1)/2  第一次移动n次，之后移动n-i次，移动一次要移动3次来交换位置。

平均时间复杂度为O(n^2)
稳定排序
*/
private static void bubbleSort(int[] array) {

int temp = 0;
for (int i=0; i<array.length; i++)
for (int j=0; j<array.length-i-1; j++) {
if (array[j] > array[j+1]){
swap(array, j, j+1);
}
}
}

/**
选择排序

从原序列选出最小的放在排序队列第一的位置，然后再从剩余未排序元素中找到最小的，放在排序队列末尾。
依次类推，直到所有元素都有序。
比较次数C，移动次数M
最好情况：正序的
比较次数C= n-1
移动次数M= 0
最坏情况：倒序
比较次数C= n*(n-1)/2   第一次比较n次，之后比较n-i次
移动次数M= 3n*(n-1)/2  第一次移动n次，之后移动n-i次，移动一次要移动3次来交换位置。

平均时间复杂度为O(n^2)
不稳定排序
*/
private static void selectSort(int[] array) {
int temp = 0;
for (int i=0; i<array.length; i++)
for (int j = i+1; j < array.length; j++) {
if (array[i] > array[j]) {
swap(array, i, j);
}
}
}

/**
插入排序

从第一个元素开始，认为该元素已经被排序，取出下一个元素，从后往前与已排序元素比较，插入其中，
并使之有序。重复进行，直到全部都排完。
插入排序包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。

最好情况：正序的
比较次数C= n-1
移动次数M= 0
最坏情况：倒序
比较次数C= n*(n-1)/2   第一次比较n次，之后比较n-i次
移动次数M= 3n*(n-1)/2  第一次移动n次，之后移动n-i次，移动一次要移动3次来交换位置。

平均时间复杂度为O(n^2)
稳定排序
*/
private static void insertSort(int[] array) {

for (int i = 1; i < array.length; i++)
for (int j = i; j > 0; j--) {
if (array[j] < array[j-1]){
swap(array, j, j-1);
}
}
}

/**
直接插入排序

算法中引进的附加记录temp称监视哨或哨兵(Sentinel)。
哨兵有两个作用：
带哨兵的插入排序中的哨兵元素有两个作用：
1、暂时存放待插入的元素,使不致于因记录后移而丢失R[i]的内容；
2、它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为array[0]与array[j],是和自己比较，
循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(for循环只有一次判断，提高了效率)。
注意：
1、有方法传进来的数组是原始数组，则插入第一个元素时，a[0]会被覆盖，造成最终排完序的数组缺少了原始数组的第一个元素（bug）。
解决方法是：在调用此方法之前，将数组做下处理，使其右移一个元素的位置，空出来的第0个元素初始化为0（或不做初始化）
2、 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。
【例】单链表中的头结点实际上是一个哨兵
3、引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于
排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。

平均时间复杂度为O(n^2)
稳定排序
*/

//无哨兵
private static void directInsertSort(int[] array) {
//直接插入排序，i从第二个开始
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i-1]) {
int temp = array[i];
int j;
for (j = i; j > 0 && temp < array[j-1]; j--) {
array[j] = array[j-1];
}
array[j] = temp;
}
}
}

//有哨兵
private static void directInsertSortGuard(int[] array) {


//用该模式，必需在调用方法之前，将原数组进行处理，所有元素后移一位，空出第一个元素，做array[0]用(哨兵)
//直接插入排序，i从第二个开始
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i-1]) {
array[0] = array[i];
int j;
for (j = i; j > 0 && array[0] < array[j-1]; j--) {
array[j] = array[j-1];
}
array[j] = array[0];
}
}
}


/**
希尔排序

将数据按不同间距，分成几组，然后对每一组进行直接插入排序。刚开始分组，增量大，之后增量越来越小，直到到为1。
希尔排序优于直接插入排序，因为，刚开始增量大时候，分组之后元素少了，再进行直接插入排序所需的移动和比较次数都减少了。
到最后增量小了，元素虽然多，但几乎都有序了，需要移动和比较的次数也少了。

平均时间复杂度为O(n^1.5)
不稳定排序
*/
private static void shellSort(int[] array) {
int d = array.length;
while(true) {
d = d/2;
for (int i = 0; i < d; i++)
//直接插入排序
for (int j = i + d; j < array.length; j += d) {
if (array[j] < array[j-d]){
int temp = array[j];
int k;

for (k = j; k >= d && array[k-d] > temp; k -= d) {
array[k] = array[k-d];
}
array[k] = temp;
}
}


System.out.println("d is " + d);

for (int i: array) {
System.out.println(i);
}


if ( d == 1) {
break;
}
}
}



/*
快速排序

以第一个元素为基准k，遍历一次数据，将所有比k大的放在其后，比k小的放在其前。
将k前和k后的子序列，分别作为初始序列，重复进行刚才的比较。直到子序列为1为止。

平均时间复杂度为O(nlog2n)
不稳定排序
*/
private static void quickSort(int[] array, int start, int end) {
int i = start;
int j = end;
//int tmp = array[i];  //以第一个数为标准，比较大小

if(array == null || array.length == 0) {
return;
}
int n = 0;
while (i < j) {

n++;
if (n >= 10)
return;
System.out.println("i = " + i + "j = " + j + " n " + n);


if (i < j && array[i] <= array[j]) {  // 从后往前找第一个比array[i]小的数，不能忘记“=”情况。
j--;
}
if (i < j) {   // 找出后，交换位置
swap(array, i, j);
}

if (i < j && array[i] < array[j]) {  // 从前往后找，第一个比array[i]大的数
i++;
}
if (i < j) {
swap(array, i, j);   // 找出后，交换位置
}
// 如果i仍然大于j，则继续循环，知道i、j相遇则完成第一次快速排序，
//将大于array[i]的数都放在前面，小于的都放在后面
}

if (i - start > 1) {   // 对前一部分递归进行快速排序
quickSort(array, start, i-1);
}

if (end - i > 1) {     // 对后一部分递归进行快速排序
quickSort(array, i+1, end);
}
}


/*
归并排序

将待排序列从中间一份为二，分成的两部分。前后两部分继续从中间分成两份，直到每个子序列都只剩一个元素为止。
这时候认为各个分好的子序列为有序的，然后将他们按大小顺序合并起来，排好序。


平均时间复杂度为O(nlogn) 需要额外的存储空间。
稳定排序
*/
public static void mergeSort(int[] array, int start, int end) {
if (start < end) {
int mid = (start + end)/2;     // 取开始和结尾的中间位置
mergeSort(array, start, mid);  // 递归进行前一部分归并排序
mergeSort(array, mid+1, end);  // 递归进行后一部分归并排序

// 二路归并
int i = start;
int j = mid + 1;
int k = 0;
int[] temp = new int[end - start + 1];  // 临时数组

// 比较逐一两个子队列，将小的元素放入临时数组中
while (i <= mid && j <= end) {
if (array[i] < array[j]) {
temp[k++] = array[i++];
}
if (array[i] >= array[j]) {
temp[k++] = array[j++];
}
}

// 执行完上一个循环之后，肯定有一个子队列都放入临时数组中
while(i <= mid) {
temp[k++] = array[i++];
}

while(j <= end) {
temp[k++] = array[j++];
}

// 将临时数组中数据，放到原数组中
k = start;
for (int element:temp) {
array[k++] = element;
}
}
}

/*
交换两个数
*/
public static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}