本文主要对一些基础排序算法进行温故。子曰：“温故而知新，可以为师矣?！?/p>
插入排序---直接插入排序
基本思想：将一个记录插入到已经排好序的有序列表中，从而得到新的有序列表。
平均时间复杂度：O(n2)
平均空间复杂度：O(1)
- 令i从i递增到n-1，重复(2)~(4)
- 将元素Si保存到临时变量中
- 确定使得条件Sj>=Si成立的最小j
- 将子序列{Sj...Sj-1}后移一个位置到{Sj+1...Sj}
- 将保存在临时变量中的Si复制到Sj+1
实现代码：
public void insertSort(int [] a){
int len = a.length;
for(int i = i;i<len-1;i++){
int temp = a[i]; //临时存储a[i]
int j = j-1; //小于i的索引，都认为是已经排好序的
while(j>=0 && temp<a[j]){
a[j+1]=a[j]; //将数据向右移动一位
j--;
}
a[j+1] = temp; //找到插入的位置，将临时存储的a[i]，赋值到j+1
}
}
插入排序---希尔排序
平均时间复杂度：O(n3/2)
平均空间复杂度：O(1)
基本思想：取一个小于n的整数d1，作为第一个增量，将数组分成d1组，在各组内进行插入排序；然后去第二个增量d2<d1，重复以上的操作，直到dt=1。
代码实现：
public void shellSort(int [] a){
int datalen = a.length/2;
while(datalen >0){
for(int i=datalen;i<a.length;i++){
int pointer = i-datalen;
int temp = a[pointer];
while(pointer>=0 && temp<a[pointer]){
a[pointer+datalen]=a[pointer];
pointer-=datalen;
}
a[pointer+datalen]=temp;
}
datalen = datalen/2;
}
}
交换排序---冒泡排序
平均时间复杂度：O(n2)
平均空间复杂度：O(1)
基本思想：根据轻气泡不能在重气泡之下的原则，从下往上扫描，凡是违背这一原则的的轻气泡就使之向上“漂浮”，直到最后任意两个气泡都是轻者在上，重者在下为至。
- 令i从n-1递减到1，重复步骤(2)~(4)
- 令j从0递增到i，重复步骤(3)
- 如果元素Sj-1和Sj成反序，交换它们
- 结束标记，序列{S0...Si}被排序且Si最大
代码实现：
public void bubbleSort(int [] a){
for(int i = a.length;i>0;i--){
for(int j = 0;j<i;j++){
if(a[j+1] < a[j]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
交换排序---快速排序
平均时间复杂度：O(nlogn)
平均空间复杂度：O(logn)
基本思想：采用了一种分治的策略，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。有3个步骤：
- 分解：将原问题分解为若干个子问题
- 求解：递归地解决这些子问题，若子问题的规模足够小，直接求解
- 组合：将各子问题的解组合原问题的解
代码实现：
public void quickSort(int [] a,int low,int hi){
if(low>=hi) return;
int j = partition(a,low,hi);
quickSort(a,low,j-1);
quickSort(a,j+1,hi);
}
public int partition(int [] a,int low,int hi){
int temp = a[low];
int i = low;
int j = hi;
while(i<j){
while(i<j;temp<a[j]){
j--;
}
exch(a,i,j);
while(i<j;temp>a[i]){
i++;
}
exch(a,i,j);
}
return j；
}
public void exch(int [] a ,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
选择排序---直接选择排序
平均时间复杂度：O(n2)
平均空间复杂度：O(1)
基本思想：在第i次排序时，有序区S[1..i-1]和无序区S[i...n]，取无序区一个最小值记录R[k]，将R[k]与无序区第一个记录交换，使得S[1..i]和S[i+1..n]成为新的有序区和无序区。
代码实现：
public void selectSort(int [] a){
for(int i = 0;i<a.length;i++){
int minVal = Integer.MAX_VALUE;
int minIndex = 0;
for(int j = i;j<a.length;j++){
int temp = a[j];
if(temp<minVal){
minVal = temp;
minIndex = j;
}
}
exch(a,i,minIndex);
}
}
选择排序---堆排序
平均时间复杂度：O(nlogn)
平均空间复杂度：O(1)
基本思想：首先堆具有下列完全二叉树的性质：每个节点的值都大于或等于其左右孩子的值，称为大顶堆；或者每个节点的值都小于等于其左右孩子的值，称为小顶堆。利用这一性质，将待排序的数据构建成一个大顶堆或者小顶堆，将根结点与数据末端的元素交互，并移除数据末端元素，然后n-1继续重构一个堆，如此反复执行。
代码实现：
public void heapSort(int len){
for(int i = len/2;i>0;i--){
heapAjust(i,len);
}
for(int i = len; i>0;i--){
exch(1,i);
heapAjust(1,i-1);
}
}
public void heapAjust(int s,int len){
int temp , j;
temp = arr[s];
for(j=2*s;j<=len;j*=2){
if(j<len && arr[j]<arr[j+1]){
j++
}
if(temp>=arr[j])
break;
arr[s] = arr[j];
s = j;
}
arr[s] = temp;
}
欢迎关注我的个人订阅号
