面试官逼问系列之：四种排序算法
请你使用java语言描述插入排序、选择排序、交换排序
插入排序
//////////////////////////////////////////// 插入排序 ////////////////////////////////////////////
/** 直接插入排序 **/
public void zhijiecharupaixu(int[] array) throws Exception {
for(int i = 0; i < array.length-1; i++){
int temp = array[i+1];
int j = i;
for(; j > -1 && temp < array[j]; j--){
array[j+1] = array[j]; //后移出temp的位置
}
array[j+1] = temp;
}
System.out.println(Arrays.toString(array));
}
/** 希尔排序 **/
public void xierpaixu(int[] array) throws Exception {
double d1 = array.length;
while(true){
d1 = Math.ceil(d1 / 2);
int d = (int) d1;
for(int x = 0; x < d; x++){
for(int i = x; i < array.length-d; i += d){//每次增加d，而不是1
int temp = array[i+d];
int j = i;
for(; j > -1 && temp < array[j]; j -= d){
array[j+d] = array[j]; //后移出temp的位置
}
array[j+d] = temp;
}
}
if(d == 1) break;
}
System.out.println(Arrays.toString(array));
}
选择排序
//////////////////////////////////////////// 选择排序 ////////////////////////////////////////////
/** 直接选择排序 **/
public void zhijiexuanzepaixu(int[] array) throws Exception {
for(int i = 0; i < array.length; i++){
int idx = i;
int temp = array[i];
for(int j = i+1; j < array.length; j++){ //选择最小的与i交换
if(array[j] < temp){
idx = j;
temp = array[j];
}
}
array[idx] = array[i];
array[i] = temp;
}
System.out.println(Arrays.toString(array));
}
/**
* 【堆排序】
* 基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。
* 堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。
* 前者为最大堆，后者为最小堆，这里只讨论最大堆。
*
* 由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。
* 完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
*
* 1. 将有n个元素的数组a按照最大堆的要求进行调整
* 2. 将栈顶a[0]元素（为最大元素）与当前最大堆的最后一个元素交换。然后将前面(n-1)个数重新调整成最大堆。重复1
* 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
*
*/
public void duipaixu(int[] array) {
// 循环建堆
for (int i = 0; i < array.length - 1; i++) {
buildMaxHeap(array, array.length-1-i); // 建堆
swap(array, 0, array.length-1-i); // 交换堆顶和最后一个元素
}
System.out.println(Arrays.toString(array));
}
/** 将数组元素a[0]~a[n]构建为最大堆 **/
private void buildMaxHeap(int[] arr, int n) {
//从第一个非叶子节点开始最大堆化
for (int i = (n - 1) / 2; i >= 0; i--) {
//k保存正在判断的节点
int k = i;
//沿左右孩子中值较大者重复向下检查
while (2*k+1 <= n) {
//k节点的左孩子节点
int j = 2 * k + 1;
//找出左右孩子节点的较大者
if (j < n && arr[j] < arr[j+1]) j++;
//如果k节点的值小于其较大的子节点的值
if (arr[k] < arr[j]) {
swap(arr, k, j); //交换他们
k = j;
} else {
break; //当前节点完成最大堆化
}
}
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
交换排序
//////////////////////////////////////////// 交换排序 ////////////////////////////////////////////
/** 向左冒泡 **/
public int[] maopaopaixu_l(int[] array) throws Exception {
int k;
for (int i = 0; i < array.length; i++) {
k = 0; //每次开始冒泡前，初始化 k 值为 0
for (int j = array.length-1; j > i; j--) {
if (array[j] > array[j-1]) {
k = 1;
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
//如果 k 值为 0，表明表中记录排序完成
if (k == 0) break;
}
System.out.println(Arrays.toString(array));
return array;
}
/** 向右冒泡 **/
public int[] maopaopaixu_r(int[] array) throws Exception {
int k;
for (int i = 0; i < array.length; i++) {
k = 0; //每次开始冒泡前，初始化 k 值为 0
for (int j = 0; j < array.length-1-i; j++) {
if (array[j] > array[j+1]) {
k = 1;
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
//如果 k 值为 0，表明表中记录排序完成
if (k == 0) break;
}
System.out.println(Arrays.toString(array));
return array;
}
/** 快速排序 **/
public void kuaisupaixu(int[] array, int left, int right) throws Exception {
if (left > right) {
return;
}
int i = left, j = right;
int temp = array[i];
while(i != j) {
//从右边找
while(array[j] >= temp && i < j) {
j--;
}
//从左边找
while(array[i] <= temp && i < j) {
i++;
}
if (i < j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
array[left] = array[i];
array[i] = temp;
kuaisupaixu(array, left, i-1);
kuaisupaixu(array, i+1, right);
System.out.println(Arrays.toString(array));
}
各种排序算法时间复杂度分析：
