【数据结构——数组（五）】常见排序算法总结

75 阅读 0 评论 50 点赞

我是靠谱客的博主完美鸭子，最近开发中收集的这篇文章主要介绍【数据结构——数组（五）】常见排序算法总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

public class sort {
private static int count = 0;
public static void main(String[] args) {
int[] a = { 4, 2, 1, 6, 3, 6, 0, -5, 1, -2 };
// Bubble(a); //冒泡
// SelectSort(a); //选择
// InsertSort(a); // 插入
// BinaryInsertSort(a); //二分
// ShellSort(a,dk,3); //Shell
QSort(a, 0, a.length - 1); // 快速
System.out.print("swap次数:" + count + "n排序结果为：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
/**
* <快速排序>
* 选取一个基准值，然后使 左边队列的值≦基准值≦右边队列的值
* 通过递归调用对左右子区间快速排序得到结果
*/
public static void QSort(int[] a, int low, int high) {
int i, j, temp;
if (low < high) {
i = low;
j = high;
temp = a[i];
while (i < j) {
while (i < j && a[j] > temp)
j--;
if (i < j) {
a[i] = a[j];
i++;
}
while (i < j && a[i] < temp)
i++;
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = temp;
QSort(a, low, i - 1);
QSort(a, i + 1, high);
}
}
/**
* 希尔排序
*/
public static int ShellSort(int[] a, int dlta[], int t) {
int count = 0;
for (int i = 0; i < t; i++) {
count = ShellInsert(a, dlta[i]);
}
return count;
}
public static int ShellInsert(int[] a, int dk) {
int i, j, count = 0;
for (i = dk + 1; i < a.length; i++) {
if (a[i] < a[i - dk])
a[0] = a[i];
for (j = i - dk; j > 0 && a[0] < a[j]; j -= dk) {
a[j + dk] = a[j];
count++;
}
a[j + dk] = a[0];
}
return count;
}
/**
* <折半插入排序（二分排序）>
* 在直接插入排序的基础上，取出下一个元素时，不是扫描插入，
* 而是通过二分查找的方式确定新元素要插入已排序中的位置，
* 再直接后移位置，插入新元素。
*/
public static void BinaryInsertSort(int[] a) {
int i, j, low, high, m, temp;
// System.out.println("******二分排序******");
for (i = 1; i <= a.length; i++) {
temp = a[i];
low = 1;
high = i - 1;
while (low <= high) {
m = (low + high) / 2;
if (temp < a[m])
high = m - 1;
else
low = m + 1;
} // while
for (j = i - 1; j > high; j--)
a[j + 1] = a[j];
a[high + 1] = temp;
}
}// BinaryInsertSort
/**
* <直接插入排序>
* 从第一个元素开始，该元素可以认为已经被排好序。
* 取出下一个元素，在已经排序的元素序列中从后往前扫描
* 如果已排序的元素大于新元素，则将该元素与后一位的新元素交换位置
*/
public static void InsertSort(int[] a) {
int i, j;
// System.out.println("******插入排序******");
for (i = 1; i < a.length; i++) {
for (j = i; j > 0 && a[j] < a[j - 1]; j--) {
swap(a, j, j - 1);
}
}
}
/**
* <冒泡排序>
* 根据大气泡不能在小气泡之下的原则，从下往上扫描数组R，
* 凡扫描到违反本原则的大气泡，就使其向上“漂浮”
*/
public static void Bubble(int[] a) {
// System.out.println("******冒泡排序******");
for (int i = 0; i < a.length - 1; i++) {
boolean exchange = false;
for (int j = a.length - 1; j > i; j--) {
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
exchange = true;
}
}
if (!exchange) {
return;
}
}
}
/**
* <选择排序>
* 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，
* 然后，再从剩余未排序元素中继续寻找最小元素，放到排序序列末尾。
* 以此类推，直到所有的元素均排序完毕。
*/
public static void SelectSort(int[] a) {
// System.out.println("******选择排序******");
for (int i = 0; i < a.length; i++) {
boolean exchange = false;
for (int j = i + 1; j < a.length; j++) {
if (a[i] > a[j]) {
swap(a, i, j);
exchange = true;
}
}
if (!exchange) {
return;
}
}
}
/**
* swap交换函数
*/
private static void swap(int[] source, int x, int y) {
count++;
int temp = source[x];
source[x] = source[y];
source[y] = temp;
/*
* for (int i = 0; i < source.length; i++) { System.out.print(source[i]
* + " "); } System.out.println();
*/
}
}