JAVA 简单排序总结

插入排序

?

?

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2~5

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

?

?

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

?

(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

?

算法描述

归并操作的过程如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

?写道public int[] Two_Way_Merge_Sort(int[] arrayA, int[] arrayB) {
int[] resultC = new int[arrayA.length + arrayB.length];
int k = 0;
int i = 0;
int j = 0;
while(i < arrayA.length && j < arrayB.length) {
if (arrayA[i] < arrayB[j])
resultC[k++] = arrayA[i++];
else
resultC[k++] = arrayB[j++];
}
while (i < arrayA.length)
resultC[k++] = arrayA[i++];
while (j < arrayB.length)
resultC[k++] = arrayB[j++];
return resultC;
}?

?

?

?