package practice.ch07;
import source.ch07.RecordNode;
/**
* @author Snail Van
*
*/
public class Sort {
/** 1.插入排序 */
public int[] insertionSort(int[] arr) {
// 依次将index>1的各数有序插入到前面
for (int i = 1; i < arr.length; i++) {
int index = i;
int temp = arr[i];// 暂存要插入的数
// 如果前一个数大，则将前一个数向后挪动一个位置，继续向前找
while (index > 0 && arr[index - 1] > temp) {
arr[index] = arr[index - 1];
index--;
}
// 找到了插入位置，将其插入
arr[index] = temp;
}
return arr;
}
/** 2.希尔排序 */
public int[] shellSort(int[] d, int[] arr) {
for (int k = 0; k < d.length; k++) {// d为增量数组
int dk = d[k];
// 实际计算时多个分组交替计算的,从第dk+1个数开始，和之前依次间隔dk的数做插入排序的插入操作
for (int i = dk; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i - dk; j >= 0 && temp < arr[j]; j -= dk) {
arr[j + dk] = arr[j];
}
arr[j + dk] = temp;
}
}
return arr;
}
/** 3.冒泡排序 */
public int[] bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
/** 4.快速排序 */
public int[] quickSort(int[] arr) {
return qSort(arr, 0, arr.length - 1);
}
// 辅助方法: 递归调用
private int[] qSort(int[] arr, int low, int high) {
// 隐含结束条件是 low == high
if (low < high) {
int pivotloc = partition(arr, low, high); // 从pivotloc位置将小的放左边，将大的放右边
qSort(arr, low, pivotloc - 1); // 将左边的递归
qSort(arr, pivotloc + 1, high);// 将右边的递归
}
return arr;
}
// 辅助方法：一次快排
private int partition(int[] arr, int i, int j) {
int pivot = arr[i];// 选第一个元素作为支点, i位置空出来了
while (i < j) {// i = j 时结束
// 从右到左找到一个比pivot小的arr[j]
while (i < j && pivot < arr[j]) {
j--;
}
// 把arr[j]放到左边i的位置，i++; j位置空出来了
if (i < j) {
arr[i] = arr[j];
i++;
}
// 从左到右找到一个比pivot大的arr[i]
while (i < j && pivot > arr[i]) {
i++;
}
// 把arr[i]放到左边j的位置，j--; i位置空出来了
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot; // 此时 i==j 将pivot赋给arr[i]
return i;
}
/** 5.选择排序 */
public int[] selectionSort(int[] arr) {
int minIndex, temp; // 写在这儿不用每次重新创建提高效率
for (int i = 0; i < arr.length - 1; i++) {
minIndex = i;
for (int j = i; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
/** 6.堆排序 */
public int[] heapSort(int[] arr) {
int len = arr.length;
int temp;
// 从最后一个非叶子节点序号开始向前依次调整顺序，创建初始堆
for (int i = len / 2 - 1; i >= 0; i--) {
sift(arr, i, len);
}
// 每趟将最小值交换到后面，再调整成堆
for (int i = len - 1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
sift(arr, 0, i);
}
return arr;
}
// 辅助方法：调整堆
private void sift(int[] arr, int low, int high) {
int i = low; // 子树根节点
int j = 2 * i + 1; // j为i结点的左孩子
int temp = arr[i];
while (j < high) { // 沿较小孩子向下筛选
if (j < high - 1 && arr[j] > arr[j + 1]) {
j++;
}
if (temp > arr[j]) {// 若父节点值较大
arr[i] = arr[j];// 孩子节点中较小值上移
i = j;
j = 2 * i + 1;
} else {
j = high + 1; // 退出循环
}
}
arr[i] = temp;
}
/** 7. 归并排序 */
public int[] mergeSort(int[] arr) {
int s = 1;
int len = arr.length;
int[] temp = new int[len]; // 开辟同等大小空间
while (s < len) {
mergepass(arr, temp, s, len);
s *= 2;
mergepass(temp, arr, s, len);
s *= 2;
}
return arr;
}
private void mergepass(int[] arr, int[] order, int s, int n) {
int p = 0;
while (p + 2 * s - 1 <= n - 1) {
merge(arr, order, p, p + s - 1, p + 2 * s - 1);
p += 2 * s;
}
if (p + s - 1 < n - 1) {
merge(arr, order, p, p + s - 1, n - 1);
} else {
for (int i = p; i <= n - 1; i++)
{
order[i] = arr[i];
}
}
}
private void merge(int[] arr, int[] order, int h, int m, int t) {
int i = h, j = m + 1, k = h;
while (i <= m && j <= t) {
if (arr[i] <= arr[j]) {
order[k++] = arr[i++];
} else {
order[k++] = arr[j++];
}
}
while (i <= m) {
order[k++] = arr[i++];
}
while (j <= t) {
order[k++] = arr[j++];
}
}
public void show(String s, int[] arr) {
System.out.print(s);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
Sort s = new Sort();
s.show("未排序前：", arr);
// s.show("插入排序：",s.insertionSort(arr));
// int[] d = {5,3,1};
// s.show("希尔排序：", s.shellSort(d, arr));
// s.show("冒泡排序：", s.bubbleSort(arr));
// s.show("快速排序：", s.quickSort(arr));
// s.show("选择排序：", s.selectionSort(arr));
// s.show("堆排序：", s.heapSort(arr));
s.show("归并排序：", s.mergeSort(arr));
}
}
转载于:https://www.cnblogs.com/snailvan/p/10653310.html
