排序 主流七大排序，
package ds;
/*
* author : codinglion
* contact: chenyakun@foxmail.com
*/
import java.util.Random;
publicclass Sorts {
// 冒泡排序
// 小数往上冒
public static int[] BubbleSort(int[] disOrderArray) {
int temp;
// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）
for (int i = 0; i < disOrderArray.length - 1; i++) {
// 把最小的数交换着"冒泡"的相对的最上边,一次冒上来的是最小的,其次是第二小的.
// length-1: 取数据最后一个数下标
// j>i 从后往前的下标一定大于从前往后的下标,否则越界了
for (int j = disOrderArray.length - 1; j > i; j--) {
if (disOrderArray[j] < disOrderArray[j - 1]) {
temp = disOrderArray[j];
disOrderArray[j] = disOrderArray[j - 1];
disOrderArray[j - 1] = temp;
}
}
}
// for (int element : disOrderArray) {
//
// System.out.print(element + " ");
// }
return disOrderArray;
}
/*
*
* 快速排序
*
* 思想:
* 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,
* 则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的
*
* 本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base
* 首先从序列最右边开始找比base小的
* ,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大
* 然后,从序列的最左边开始找比base大的
* ,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小
*
* 循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归
*/
public static int[] quickSort(int[] arr, int low, int heigh) {
if (low < heigh) {
int division = partition(arr, low, heigh);
quickSort(arr, low, division - 1);
quickSort(arr, division + 1, heigh);
}
return arr;
}
// 分水岭,基位,左边的都比这个位置小,右边的都大
public static int partition(int[] arr, int low, int heigh) {
int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录
while (low < heigh) { //从表的两端交替向中间扫描
while (low < heigh && arr[heigh] >= base) {
heigh--;
}
// base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大
swap(arr, heigh, low);
while (low < heigh && arr[low] <= base) {
low++;
}
// 遇到左边比base值大的了,换位置
swap(arr, heigh, low);
}
// now low = heigh;
return low;
}
private static void swap(int[] arr, int a, int b) {
int temp;
temp = arr[a];
arr[a] = arr;
arr = temp;
}
/*
*
* 直接选择排序
*/
public static int[] selectionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int miniPos = miniPos(arr, i, arr.length);
if (arr > arr[miniPos]) {
swap(arr, i, miniPos);
}
}
returnnull;
}
// 返回最小的时序列中的哪一位
public static int miniPos(int[] arr, int from, int end) {
int miniPost = from;
for (int i = from + 1; i < end; i++) {
if (arr < arr[miniPost]) {
miniPost = i;
}
}
return miniPost;
}
/*
* heap sort 堆排序
*/
// 本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点
// 把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换
// 剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆
// 递归
public static int[] heapSort(int[] arr) {
int i;
// 将arr构成一个大顶堆
// 从 0 到 arr.length/2 ,这些都是有孩子的节点
// 没孩子的节点构造大顶堆就无意义了
for (i = arr.length / 2; i >= 0; i--) {
heapAdjust(arr, i, arr.length - 1);
}
for (i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
// 将arr[0...i-1] 重新构造成一个大顶堆
heapAdjust(arr, 0, i - 1);
}
return arr;
}
private static void heapAdjust(int[] arr, int s, int m) {
int temp, j;
temp = arr; // 指向临时(相对与root节点)的根节点
for (j = 2 * s; j <= m; j *= 2) {
// 如果右节点比左节点大,当前节点移到右节点
if (j < m && arr[j] < arr[j + 1]) {
// 指向右节点
j++;
}
// 当前的父节点大于现在指向的节点
// 不需要做任何处理
if (temp >= arr[j]) {
break;
}
// 当前的父节点小于其下的子节点
// 换位置,把这个子节点替换到父节点
// 当前这个位置,如果是叶子节点,则它应该是最小的(相对于它的祖先们)
// 这个方法目的就是交换parent与children的值,构造大根堆
// 执行到这里表明当前节点的父节点(临时根节点小于当前的节点),
// 把当前节点移到上面,换位置
// arr被覆盖无所谓,因为temp记了这个值(原来的根节点(相对的parent))
arr = arr[j];
// 现在把当前的这个元素,看做是临时的parent节点
// 为了找到此时这个元素的孩子节点,看看是否有比当前这个值还大的
// 最后s指向 当前遍历到的这个元素
s = j;
}
arr = temp;
}
/*
* 插入排序
* 思想: 扑克牌
* 从无序序列往有序子序列插入, 插入排序改进版 不足: 移动太频繁
*/
public static int[] InsertSort(int[] arr) {
// 无序序列
// 忽略首位,从1开始
for (int i = 1; i < arr.length; i++) {
int temp = arr;
int j;
// 有序序列
// 最早从0开始比对
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
// j 后面的往后挪
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
return arr;
}
/*
* SHELL 希尔排序
* 插入排序改进版
*
*/
public static int[] ShellSort(int[] arr) {
// 取增量
int step = arr.length / 2;
while (step >= 1) {
// 还是忽略0位
// 0...step 1...step+1
for (int i = step; i < arr.length; i++) {
int temp = arr;
int j = 0;
// 跟插入排序的区别就在这里
for (j = i - step; j >= 0 && temp < arr[j]; j -= step) {
arr[j + step] = arr[j];
}
arr[j + step] = temp;
}
step /= 2;
}
return arr;
}
/*
*
*归并排序
*分到最细了,就剩两个数,归并,依次类推
* 本质是靠归并(有序的merge)排的序
*
*/
public static int[] mergeSort(int[] arr, int[] tempArray, int left,
int right) {
if (left < right) {
// 取分割位置
int middle = (left + right) / 2;
// 递归划分数组左序列
mergeSort(arr, tempArray, left, middle);
// 递归划分数组右序列
mergeSort(arr, tempArray, middle + 1, right);
Merge(arr, tempArray, left, middle + 1, right);
}
return arr;
}
private static void Merge(int[] arr, int[] tempArray, int left, int middle,
int right) {
int leftEnd = middle - 1;
int rightStart = middle;
// 临时数组的下标
int tempIndex = left;
// 数组合并厚的length长度
int tempLength = right - left + 1;
// 先循环两个区间段都没有结束的情况
while ((left <= leftEnd) && (rightStart <= right)) {
// 左边的比右边的小,先插入左边的
if (arr[left] < arr[rightStart]) {
tempArray[tempIndex++] = arr[left++];
} else {
tempArray[tempIndex++] = arr[rightStart++];
}
}
// 判断左序列是否结束
while (left <= leftEnd) {
tempArray[tempIndex++] = arr[left++];
}
// 判断右序列是否结束
while (rightStart <= right) {
tempArray[tempIndex++] = arr[rightStart++];
}
// 交换数据
for (int i = 0; i < tempArray.length; i++) {
arr[right] = tempArray[right];
right--;
}
}
public static void main(String[] args) {
int[] arr // = { 5, 9, 3, 7, 2, 1,6 };
= new int[100];
Random random = new Random();
random.setSeed(System.currentTimeMillis());
for (int i = 0; i < 100; i++) {
arr = random.nextInt(1000);
}
System.out.println("begin");
// quickSort(arr, 0, arr.length - 1);
// selectionSort(arr);
InsertSort(arr);
for (int e : arr) {
System.out.print(e + " ");
}
}
} |
收藏
淘帖
踩
