几种基础排序的学习
冒(冒泡)>选(选择)>插(插入)>希(希尔)>快(快速)>归(归并)>堆
时间复杂度
冒-O(n^2)
选-O(n^2)
插-O(n^2)
希-O(n*logn)
快-O(n*logn)
归-O(n*logn)
堆-O(n*logn)
(1)冒泡排序:
package com.jp.algorithm.sort;
/**
* 1. 冒泡排序
* @author hadoop
*
*/
public class BubbleSort {
public static void main(String[] args) {
// 整数类型数组（原始数据类型）,随便定义
int[] numbs = { 87, 25, 4, 22, 2, 56, 11, 28, 35, 15 };
// 定义一个临时交换变量
int temp = 0;
for (int i = 0; i < numbs.length; i++) {
for (int j = 0; j < numbs.length - 1; j++) {
if (numbs[i] < numbs[j]) {
// 没有动作
} else {
temp = numbs[i];
numbs[i] = numbs[j];
numbs[j] = temp;
}
}
}
// 打印冒泡排序过后的数组
for (int i = 0; i < numbs.length; i++) {
System.out.println(numbs[i]);
}
}
}
(2)选择排序:
package com.jp.algorithm.sort;
/**
* 2.选择排序
*
* 从所有的当中选择出要得放到一头
*
* @author peng.jia
*
*/
public class SelectSort {
public static void Sort(int[] sort) {
for (int i = 0; i < sort.length - 1; i++) {
for (int j = i + 1; j < sort.length; j++) {
if (sort[i] > sort[j]) {
int temp;
temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
}
}
public static void main(String[] args) {
int[] sort = { 8, 5, 7, 9, 55 };
for (int i = 0; i < sort.length; i++) {
System.out.print(sort[i] + " ");
}
Sort(sort);
System.out.println("\n================= ");
for (int i = 0; i < sort.length; i++) {
System.out.print(sort[i] + " ");
}
}
}
(3)插入排序:
package com.jp.algorithm.sort;
/**
* 3.插入排序
*
* @author peng.jia
*
*/
public class InsertSort {
// 插入排序法
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;
}
}
public static void main(String[] args) {
int[] array = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
sort(array);
System.out.println("\n================= ");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
(4)希尔排序:
package com.jp.algorithm.sort;
/**
*
*
* 4.希尔排序-先对位排序再插入排序
*
* 希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
* 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强 版的插入排序 拿数组5, 2, 8,
* 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
* 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
* 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
*
* @author peng.jia
*
*/
public class ShellSort {
public static void shellSort(int[] data) {
int j = 0;
int temp = 0;
for (int increment = data.length / 2; increment > 0; increment /= 2) {
for (int i = increment; i < data.length; i++) {
temp = data[i];
for (j = i; j >= increment; j -= increment) {
if (temp > data[j - increment]) {
data[j] = data[j - increment];
} else {
break;
}
}
data[j] = temp;
}
}
}
public static void main(String[] args) {
int[] data = new int[] { 5, 2, 8, 9, 1, 3, 4 };
System.out.println("未排序前");
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
shellSort(data);
System.out.println("\n排序后");
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}
(5)快速排序:
package com.jp.algorithm.sort;
/**
* 5.快速排序-左右换,直到换到中间分裂
*
* @author peng.jia
*
*/
public class QuickSort {
/**
* @param pData
* 需要排序的数组
* @param left
* 左边的位置,初始值为0
* @param right
* 右边的位置,初始值为数组长度
*/
public static void QuickSort(int[] pData, int left, int right) {
int i, j;
int first, temp;
i = left;
j = right;
first = pData[left]; // 这里选其他的数也行，不过一般选第一个
// 一趟快速排序
while (true) {
// 从第二个数开始找大于中枢的数 ,从前面开始找大于pData[left]的数
while ((++i) < right - 1 && pData[i] < first)
;
// 从最后一个数开始找第一个小于中枢pData[left]的数
while ((--j) > left && pData[j] > first)
;
if (i >= j)
break;
// 交换两边找到的数
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
}
// 交换中枢
pData[left] = pData[j];
pData[j] = first;
// 递归快排中枢左边的数据
if (left < j)
QuickSort(pData, left, j);
// 递归快排中枢右边的数据
if (right > i)
QuickSort(pData, i, right);
}
public static void main(String[] args) {
final int SORT_COUNT = (int) (Math.random() * 10 + 1);// 参与排序的数字数量随机产生
int[] pData = new int[SORT_COUNT];
for (int i = 0; i < SORT_COUNT; i++)
pData[i] = (int) (Math.random() * 100);// Produce 10 random integers
for (int i = 0; i < pData.length; i++) {
System.out.print(pData[i] + " ");
}
QuickSort.QuickSort(pData, 0, pData.length);
System.out.println("\n***********************");
for (int i = 0; i < pData.length; i++) {
System.out.print(pData[i] + " ");
}
}
}
(6)归并排序:
package com.jp.algorithm.sort;
/**
* 6.归并排序-最小两两合并,不断壮大排序集
*
* @author peng.jia
*
*/
public class MergeSort {
/**
* 归并排序 先将初始的序列表看成是n个长度为1的有序表 (1)定义指针i,指向第一个序列表的第一个元素
* (2)定义指针j，指向第二个序列表的第一个元素 (3)比较i,j指向的元素大小，若前者大，将后者插入到新表中 否则，把前者插入到新表中
* (4)直到取完第一个序列表或者第二个序列表为止
*
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num = { 51, 38, 49, 27, 62, 05, 16 };
int[] num1 = new int[7];
num = mergesort(num, 0, num.length - 1, num1);
for (int i : num) {
System.out.print(i + " ");
}
}
private static int[] mergesort(int[] num, int s, int t, int[] num1) {
int m;
int[] num2 = new int[t + 1];
if (s == t)
num1[s] = num[s];
else {
m = (s + t) / 2;
mergesort(num, s, m, num2);// 左半部分递归调用
mergesort(num, m + 1, t, num2);// 右半部分递归调用
merg(num2, s, m, t, num1);// 由num2去归并，返回的值放到num1中,num1赋新值，其实就是更新num2,然后让num2再去归并，返回新的num1
}
return num1;
}
// 有序表的合并
private static void merg(int[] num, int l, int m, int n, int[] num1) {
System.out.print("l=" + l + " m=" + m + " n=" + n);
System.out.println();
int i, j, k;
i = l;
j = m + 1;
k = l;
while (i <= m && j <= n) {
if (num[i] < num[j])
num1[k++] = num[i++];
else {
num1[k++] = num[j++];
}
}
while (i <= m) {
num1[k++] = num[i++];
}
while (j <= n) {
num1[k++] = num[j++];
}
}
}
(7)堆排序
package com.jp.algorithm.sort;
/**
* 7.堆排序-先建树,再找树根,找到根就换成叶子,再找根...
*
* 堆排序包括两个步骤 (1)初始堆(堆的定义：(1)堆是一个完全二叉树(2)根结点的值或者大于左右子树的值或者小于左右子树的值(3)左右子树也是一个堆)
* (2)调整堆(当初始小顶堆之后，堆顶元素是最小的元素，取出最小的元素与最后一个元素相交换，再把剩下n-1个元素调整成堆,依次调整直到1为止)
* 非终端节点调整 初始堆时从n/2向上调整成堆 把第一个元素与最后一个元素交换之后从第1个元素开始调整成新堆
*
* @author peng.jia
*
*/
public class HeapSort {
public static void main(String[] args) {
int num[] = new int[] { 1, 5, 40, 32, 2, 2221 };
heapsort(num, 5);
for (int x = 0; x < num.length - 1; x++) {
System.out.print(num[x + 1] + " ");
}
}
// 调整堆
public static void adjustHeap(int[] num, int s, int t) {
int i = s;
int x = num[s];
for (int j = 2 * i; j <= t; j = 2 * j) {
if (j < t && num[j] < num[j + 1])
j = j + 1;// 找出较大者把较大者给num[i]
if (x > num[j])
break;
num[i] = num[j];
i = j;
}
num[i] = x;
}
public static void heapsort(int[] num, int n) {
// 初始建堆从n/2开始向根调整
int i;
for (i = n / 2; i >= 1; i--) {
adjustHeap(num, i, n);// 初始堆过程
}
for (i = n; i > 1; i--) {
num[0] = num[i];// 将堆顶元素与第n,n-1,.....2个元素相交换
num[i] = num[1];
num[1] = num[0];// 从num[1]到num[i-1]调整成新堆
adjustHeap(num, 1, i - 1);
}
// java.util.concurrent.CopyOnWriteArrayList<E>
}
}
原文：http://www.cnblogs.com/really-dt/p/3797695.html