/**
* 直接插入排序
* 说的简单点，就是一组无序序列{A1,A2,........An} 先取出A1，然后从A2与A1比较,比较完之后序列状况是{A1,A2}{A3..........An},
* 其中{A1,A2}有序， 然后取出A3 ，放到{A1,A2}有序序列合适位置，
* 导致{A1,A2,A3}{A4........An}。重复这个过程，直到取出An放入{A1,A2........An-1}有序序列中。
* @param a 要排序的数组
*/
public void insertSort(int[] a) {
int len = a.length;// 数组的长度，提升效率
int num;//要插入的数据
for (int i = 1; i < len; i++) {
num = a[i];
int k = i - 1;
//从后向前将大于num的数据全部后移
while (k >= 0 && a[k] > num) {
a[k + 1] = a[k];
k--;
}
//找到位置后，插入num
a[k + 1] = num;
}
}
/**
* 希尔排序
* 现在有一个array,希尔排序就是设定一个增量incrementNum(0<incrementNum<array.length)。
* 先从array[0]开始，以incrementNum为增量的进行直接插入排序，直到数组末尾，然后从array[1]开始重复：以incrementNum为增量的进行直接插入排序; 然后从array[1]开始重复......一直到array[n]。
* 然后取一个小于上一步增量的新的增量（比如设置为incrementNum/2）,对前一个步骤的结果array进行遍历，直接插入排序....
* 再取小于上一步增量的新的增量，重复进行：遍历，直接插入排序
* 直到新的增量小于1之后再退出循环
* @param a 要排序的数组
*/
public void sheelSort(int[] a) {
int len = a.length;
int increment = len / 2;
while (increment >= 1) {
for (int i = 0; i < len; i++) {
for (int k = i; k < len - increment; k += increment) {
if (a[k] > a[k + increment]) {
int temp = a[k + increment];
a[k + increment] = a[k];
a[k] = temp;
}
}
increment = increment / 2;
}
}
}
/**
* 冒泡排序
* 冒泡排序，就是每次遍历都会把最小(或者最大)的数放在前面。
* 比如要升序{A1,........An} 第一次排序要取出整个数组中最小放在A1的位置，
* 从An开始往前遍历，相邻两个数比较，如果Aj < Aj-1 则换位,直到比较到A1 这一趟完事之后， A1放的就是整个数组中最小的数。
* 然后从A2位置开始比较，重复上一个步骤，一直比较到A2，这时候A2中放的就是整个数组中第二个小的数...........
*
* @param a 要排序的数序，升序排列
*/
public void bubbleSort(int[] a) {
int len = a.length;
for (int i = 0; i < len; i++) {
for (int m = len - 1; m >= i; m--) {
if (a[m] < a[m - 1]) {
int temp = a[m - 1];
a[m] = a[m - 1];
a[m - 1] = temp;
}
}
}
}
/**
* 快速排序
* 基本思想：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），
* 然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，
* 发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，
* 当前半部分和后半部分均有序时该数组就自然有序了。
* @param a 排序数组
* @param leftIndex 左边开始查询的下标
* @param rightIndex 右边开始查询的下标
*/
public void quickSort(int[] a, int leftIndex, int rightIndex) {
int i = leftIndex;//左边查询下标
int j = rightIndex;//右边查询下标
int temp = a[leftIndex];//基准数值
if (leftIndex > rightIndex) {
return;
}
while (i < j) {
//先从右边向左查询，找到第一个比temp小的值
while (a[j] >= temp && i < j) {
j--;
}
//从左边向右查询，找到第一个比temp大的值
while (a[i] <= temp && i < j) {
i++;
}
//满足条件，则交换两个位置的值
if (i < j) {
int t = a[j];
a[j] = a[i];
a[i] = t;
}
}
//交换基准位置的值
a[leftIndex] = a[i];
a[i] = temp;
//左边再次来一遍查询排序
quickSort(a, leftIndex, j - 1);
//右边再次来一遍查询排序
quickSort(a, j + 1, rightIndex);
}
/**
* 选择排序
* 每趟找出余下数组中最小的放在前边
*
* @param a 数组
*/
private void selectSort(int[] a) {
int len = a.length;
for (int i = 0; i < len; i++) {//循环次数
int num = a[i];
int position = i;
//循环找到最小的值，和下标index
for (int k = i + 1; k < len; k++) {
if (a[k] < num) {
num = a[k];
position = k;
}
}
//交换找到的最小值和当前的位置，放在前边
a[position] = a[i];
a[i] = num;
}
}
/**
* 前提条件：已排序的数组中查找
* 首先确定该查找区间的中间点位置： int mid = (low+upper) / 2；
* 然后将待查找的值与中间点位置的值比较：若相等，则查找成功并返回此位置。
* 若中间点位置值大于待查值，则新的查找区间是中间点位置的左边区域。
* 若中间点位置值小于待查值，则新的查找区间是中间点位置的右边区域。下一次查找是针对新的查找区间进行的。
* 递归实现二分查找
* @param a 数组
* @param start 开始位置
* @param end 结束位置
* @param key 要查找的key
* @return
*/
private int binSearch(int[] a, int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (a[mid] == key) return mid;
if (start > end) {
return -1;
} else if (key < a[mid]) {
return binSearch(a, start, mid - 1, key);
} else if (key > a[mid]) {
return binSearch(a, mid + 1, end, key);
}
return -1;
}
/**
* 普通循环实现二分查找
* @param a 数组
* @param key 要查找的key
* @return
*/
private int binSearch(int[] a, int key) {
int mid = a.length / 2;
if (a[mid] == key) {
return mid;
}
int start = 0;
int end = a.length - 1;
while (start < end) {
mid = (end - start) / 2 + start;
if (key < a[mid]) {
end = mid - 1;
} else if (key > a[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
网友评论