package test;
public class first {
/*普通的插入排序*/
public void insertSort(int[] list) {
int i, j;
list[0] = -999;//相当于设置一个监视哨兵，不用判断是否越界，但要求数组从第二个数开始即i=1开始存储
for (i = 1; i < list.length; i++) {
j = i;
while (list[j] < list[j - 1]) {
int temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
j = j - 1;
}
}
}
/*折半插入，在直接插入的基础上，添加二叉查找*/
public void binInsertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++)
{
int temp = r[i]; // 保存待插入元素
int hi = i - 1;
int lo = low; // 设置初始区间
while (lo <= hi)
{ // 折半确定插入位置
int mid = (lo + hi) / 2;
if (temp < r[mid])
hi = mid - 1;
else
lo = mid + 1;
}
for (int j = i - 1; j > hi; j--)
r[j + 1] = r[j]; // 移动元素
r[hi + 1] = temp; // 插入元素
}
}
/*希尔排序或shell */
public void shellSort(int[] r, int low, int high, int[] delta){
for (int k=0;k<delta.length;k++)
shellInsert(r, low, high, delta[k]);
}
private void shellInsert(int[] r, int low, int high, int deltaK){
for (int i=low+deltaK; i<=high; i++)
if (r[i]<r[i-deltaK]){
int temp = r[i];
int j = i-deltaK;
for(; j>=low&&temp<r[j]; j=j-deltaK)
r[j+deltaK] = r[j];
r[j+deltaK] = temp;
}
}
/*简单的选择交换*/
public void selectSort(int[] r, int low, int high) {
for (int k = low; k < high - 1; k++) { // 作n-1 趟选取
int min = k;
for (int i = min + 1; i <= high; i++)
// 选择关键字最小的元素
if (r[i] < r[min])
min = i;
if (k != min) {
int temp = r[k]; // 关键字最小的元素与元素r[k]交换
r[k] = r[min];
r[min] = temp;
}// end of if
}
}
/*堆排序-大顶堆*/
public void heapSort(int[] r){
int n = r.length - 1;
for (int i=n/2; i>=1; i--)
heapAdjust(r,i,n);
for (int i=n; i>1; i--){
int temp = r[1];
r[1] = r[i];
r[i] = temp;
heapAdjust(r,1,i-1);
}
}
//调整堆
private void heapAdjust(int[] r, int low, int high){
int temp = r[low];
for (int j = 2 * low; j <= high; j = j * 2) {
if (j < high && r[j] < r[j + 1])
j++;
if (temp > r[j])
break;
r[low] = r[j];
low = j;
}
r[low] = temp;
}
public static void main(String[] args) {
first fs = new first();
int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4, 3, 2, 1 };
int[] k={5,3,1};
// fs.insertSort(a);
//fs.binInsertSort(a, 0, a.length - 1);
//fs.shellSort(a, 0,a.length-1,k);
//fs.selectSort(a, 0, a.length-1);
fs.heapSort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
插入排序、交换排序、选择排序、归并排序等排序方法，都有一个共同的特
点，那就是它们都是通过比较元素的大小来确定元素之间的相对位置的，即上述排序方法都
是基于比较的排序方法。下面，我们就基于比较的排序方法进行一个对比和总结。
我们主要从算法的平均时间复杂度、最坏时间复杂度、空间复杂度以及排序的稳定性等
方面，对各中排序方法加以比较。
排序方法 平均时间复杂度最坏时间复杂度空间复杂度 稳定性
直接插入排序 Ο(n2) Ο(n2) Ο(1) 稳定
起泡排序 Ο(n2) Ο(n2) Ο(1) 稳定
209
快速排序 Ο(n log n) Ο(n2) Ο(log n) 不稳定
简单选择排序 Ο(n2) Ο(n2) Ο(1) 不稳定
堆排序 Ο(n log n) Ο(n log n) Ο(1) 不稳定
归并排序 Ο(n log n) Ο(n log n) Ο(n) 稳定
从时间性能上看，快速排序是所有排序算法中实际性能最好的，然而快速排序在最坏情
况下的时间性能不如堆排序和归并排序。这一点可以通过对快速排序进行改进来避免，一种
通过随机选择枢轴元素的随机快速排序，可以使得出现最坏情况出现的几率非常小，在实际
的运用中可以认为不存在。在堆排序和归并排序的比较中，当n 较大时，归并排序所需时间
较少，然而它需要较多的辅助存储空间。
从方法稳定性上来看，大多数时间复杂度为Ο(n2)的排序均是稳定的排序方法，除简单
选择排序之外。而多数时间性能较好的排序方法，例如快速排序、堆排序、希尔排序都是不
稳定的。一般来说，排序过程中的比较是在相邻的两个元素之间进行的排序方法是稳定的。
并且，排序方法的稳定性是由方法本身决定的，对于不稳定的排序方法而言，不管其描述形
式如何，总能找到一种不稳定的实例。
综上所述，上面讨论的所有排序方法中，没有哪一个是绝对最优的，在实际的使用过程
中，应当根据不同情况选择适当的排序方法。