插入算法很多，无论是在内功修炼，各种笔试面试都是相当有用的。接下来，将陆续将各种排序算法进行练习：@H_403_2@
@H_403_2@
主要分为以下几个部分（其他后面学习补充）：@H_403_2@
@H_403_2@一、插入类排序：1、直接插入排序（折半插入排序）；2、希尔shell排序；3、二叉树排序；@H_403_2@
@H_403_2@二、交换类排序：1、冒泡排序 ；2、快速排序；@H_403_2@
@H_403_2@三、选择类排序：1、简单选择； 2、堆排序；@H_403_2@
四、归并排序五、分配排序（箱排序、基数排序）@H_403_2@
@H_403_2@
所需辅助空间最多：@H_403_2@归并排序@H_403_2@
所需辅助空间最少：堆排序@H_403_2@
本人多使用Java——开始吧！@H_403_2@
首先推荐1、维基百科《排序算法》词条，图文并茂，很形象！2、学习博文《维基百科上的算法和数据结构链接很强大》，资料很多，保存学习！@H_403_2@
@H_403_2@
【数据结构】——排序算法——1.1、直接插入排序@H_403_2@
@H_403_2@
一、先上维基的图：@H_403_2@
@H_301_82@@H_403_2@ @H_301_82@图一、插入排序例子@H_403_2@| 分类@H_403_2@ | 排序算法 |
|---|---|
| 数据结构@H_403_2@ | 数组 |
| 最差时间复杂度@H_403_2@ | @H_403_2@ |
| 最优时间复杂度@H_403_2@ | @H_403_2@ |
| 平均时间复杂度@H_403_2@ | @H_403_2@ |
| 最差空间复杂度@H_403_2@ | 总共，需要辅助空间 @H_403_2@ |
@H_403_2@
二、描述@H_403_2@
@H_403_2@很简单，类似打扑克牌时按从小到大排。每次派牌的人发一张，就拿上来整理一下。拿起新派的牌，第一件事，便是看牌的大小，然后从手里整理好的牌按从大到小（或者从小到大）的方向查询。当找到一个位置同时满足一边大于等于新牌、而另外一边小于等于新牌，那就将新牌插入这个位置。重复，最后牌就排好序了！@H_403_2@
@H_403_2@
三、Java程序@H_403_2@
@H_403_2@
@H_403_2@
public class Insertion {
public static void insertionSort(Comparable []data) {
for(int index = 1; index < data.length; index++) {
Comparable key = data[index];
int position = index;
//shift larger values to the right
while (position > 0 && data[position - 1].compareTo(key) > 0) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
public static void main(String []args) {
Comparable []c = {4,9,23,1,45,27,5,2};
insertionSort(c);
for(int i = 0; i < c.length; i++)
System.out.println("插入排序：" + c[i]);
}
}
@H_403_2@
@H_403_2@
public class BinaryInsertion {
public int[] binSort(int r[],int n) {
for(int i=1;i<n;i++)
{
int temp=r[i];
int low=0;
int high=i-1;
while(low<=high)
{
int mid=(low+high)/2; //折半
if(temp<r[mid])high=mid-1; //插入点在低半区
else low=mid+1; //插入点在高半区
}
System.out.println("low:"+low+" high:"+high);
for(int j=i-1;j>=high+1;j--)
{
r[j+1]=r[j];
}
r[high+1]=temp;
}
return r;
}
public static void main(String[] args) {
int[] test = { 844,52,13,8,55,97,33,777,87,6,1 };
test = new BinaryInsertion().binSort(test,test.length);
for (int i : test) {
System.out.print(i+" ");
}
}
}
