面试题之常用排序算法(二)
移动
* */
// for(int j=0; j
// if(array[i]
// int temp = array[i];
// int k = i;
// while(k>j) {
// array[k] = array[k-1];
// k--;
// }
// array[j] = temp;
// break;
// }
// }
/*
* 第二种方法，从后往前搜索，直到找到一个比它小的元素
* 同样将这个元素往后所有已排序序列中的元素向后移动
* */
int temp = array[i];
int j = i;
if(array[j-1]>temp) {
while(j>=1 && array[j-1]>temp) {
array[j] = array[j-1];
j--;
}
}
//将这个元素赋值给相应位置
array[j] = temp;
}
}
5.选择排序
这个选择排序和插入排序看上去很像，都是从未排序的序列中选择一个元素，然后插入到已排序序列中。不过它们有很大的不同，选择排序是从待排序序列中选择
一个最小的元素，然后将这个元素插入到已排序序列的最后，这个方法的优点是，不需要频繁的在数组中移动数据，只需要两两交换即可。
基本思想： 第一步：从待排序序列中通过比较，找到最小的元素，记录其位置和值
第二步：将这个元素与待排序序列的第一个元素（也就是已排序序列最后元素的下一个元素）交换值。重复上述两步，直到所有元素已排完。
排序过程示例：
代码示例：
[java]
public void selectSort(int[] array) {
or(int i=0; i
int loc = i;
int min = array[i];
//在待排序序列中找到最小的元素
for(int j=i+1; j
6.归并排序
if(min>array[j]) {
min = array[j];
loc = j;
}
}
if(loc != i) {
array[loc] = array[i];
array[i] = min;
}
}
基本思想：将待排序序列分为的两部分，然后对这两部分分别排序，最后将两部分按某种方法合并。排序的过程是一个递归的过程。归并法是算法中分治法的一个典型代表。因此，归并排序也分为两部分，分的过程和治（合并）的过程。
合并使用的方法是：比较两个队列的队首元素，将小的从该队列中移除并插入到新队列的第一个位置，然后在比较两队列的首元素大小，将小的从该队列移除并将其添加到新队列上次添加的元素的后面，重复第二步知道有一个队列为空。将不为空的队列剩下所有的元素依次添加到新队列的最后。
排序过程示例：
第一次分割：｛3, 4, 63, 2｝｛-9, 0, 1, 32, -2｝
下面以分割后的第一部分为例。
第二次分割：｛｛3，4｝｛63， 2｝｝ 第三次分割：｛｛｛3｝｛4｝｝｛｛63｝｛2｝｝｝
合并的过程：第一次合并：｛｛3，4｝｛2，63｝｝ 第二次合并：｛2，3，4，63｝至此，第一部分已经排序完毕，第二部分排序方法相同，为｛-9，-2，0，1，32｝
最后将两部分合并为：｛-9，-2，0，1，2，3，4，32，63｝
代码示例：
[java]
private void MergeSort(int[] array, int start, int end) {
if(start == end) {
return;
}
int middle = (end - start + 1)/2 + start;
//分的过程
MergeSort(array, start, middle-1);
MergeSort(array, middle, end);
//合并的过程
merge(array, start, middle, end);
}
private void merge(int[] array, int start, int middle, int end) {
int i = start, j = middle, loc = 0;
int[] copy = new int[end-start+1];