java经典算法排序
很久没有写几种排序方法了，今天重现再一次温习了一下 主要是选择排序、冒泡排序、插入排序
选择排序
原理:a 将数组中的每个元素,与第一个元素比较
如果这个元素小于第一个元素, 就将这个
两个元素交换.
b 每轮使用a的规则, 可以选择出一个最小元素
放到第一个位置.
c 经过n-1轮比较完成排序
简单说: 每轮选择最小的放到前面.
实例代码
public class SelectSort {
/**
* @deprecated 选择排序的练习
* @author wangliang
*
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
SelectSort insertSort = new SelectSort();
insertSort.select(intgArr);
for(Integer intobj:intgArr)
{
System.out.print(intobj+" ");
}
}
/**
* @deprecated 交换数据
* @author wangliang
* @param intgArr
* @param x
* @param y
*
* */
public static void swap(Integer[] intgArr, int x, int y) {
int temp;
temp = intgArr[x];
intgArr[x] = intgArr[y];
intgArr[y] = temp;
}
/**
* @deprecated 排序算法的实现，对数组中指定的元素进行排序
* @author wangliang
* @param array待排序的数组
* @param from
* 从哪里开始排序
* @param end
* 排到哪里
* @param c
* 比较器
*/
public void select(Integer[] array) {
int minIndex;// 最小索引
/**
* * 循环整个数组（其实这里的上界为 array.length - 1 即可，因为当 i= array.length-1
* * 时，最后一个元素就已是最大的了，如果为array.length时，内层循环将不再循环），每轮假设
* * 第一个元素为最小元素，如果从第一元素后能选出比第一个元素更小元素，则让让最小元素与第一 *
* 个元素交换
*/
for (int i = 0; i < array.length; i++) {
minIndex = i;// 假设每轮第一个元素为最小元素
// 从假设的最小元素的下一元素开始循环
for (int j = i + 1; j < array.length; j++) {
// 如果发现有比当前array[smallIndex]更小元素，则记下该元素的索引于smallIndex中
if ((array[j].compareTo(array[minIndex])) < 0) {
minIndex = j;
}
}
// 先前只是记录最小元素索引，当最小元素索引确定后，再与每轮的第一个元素交换
swap(array, i, minIndex);
}
}
}
冒泡排序
原理: a 逐一比较数组中相邻的两个元素, 如果后面
的数字小于前面的数字, 就交换先后元素.
b 经过一个轮次的比较, 一定有一个最大的排
在最后的位置.
c 每次比较剩下的元素, 经过n-1次比较, 可以
实现排序
简单说: 比较交换相邻元素,每次最大的漂移到最后
示例代码
public class BubbleSort {
/**
* @param args
* @author wangliang
* @deprecated 冒泡排序的练习
*/
public static void main(String[] args) {
int[] values = { 3, 1, 6, 2, 9, 0, 7, 4, 5 };
sort(values);
for (int i = 0; i < values.length; i++) {// 排序后打印数组中的元素
System.out.println("Index: " + i + " value: " + values[i]);
}
}
/**
* @param int[] values
* @deprecated 排序
* @author wangliang
*
* */
public static void sort(int[] values) {
int temp;
for (int i = 0; i < values.length; i++) {// 趟数
for (int j = 0; j < values.length - i - 1; j++) {// 比较次数
if (values[j] > values[j + 1]) {
temp = values[j];
values[j] = values[j + 1];
values[j + 1] = temp;
原理: a 将数组分为两部分, 将后部分的第一张逐一
与前部分每一张比较, 如果当前元素小, 就
一点被比较元素.
b 找到合理位置插入.
}
}
}
}
}
插入排序
原理: a 将数组分为两部分, 将后部分的第一张逐一
与前部分每一张比较, 如果当前元素小, 就
一点被比较元素.
b 找到合理位置插入.
示例代码
public class InsertSort {
/**
* @param args
* @author wangliang
* @deprecated 插入排序的练习
*/
public static void main(String[] args) {
int[] arr = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
InsertSort is = new InsertSort();
is.sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
/**
* @author wangliang
* @deprecated 排序比较
* @param arr
* []
*
* */
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
// insertValue准备和前一个数比较
int index = i - 1;
while (index >= 0 && insertVal < arr[index]) {
// 将把arr[index]向后移动
arr[index + 1] = arr[index];
// 让index向前移动一位
index--;
}
// 将insertValue插入到适当位置
arr[index + 1] = insertVal;
}
}
}