冒泡排序
public class MaoPaoSort {
public static void main(String[] args) {
int[] a = { 28, -30, 25, 70, 6,2,3,4,5,6,234,-234 };
// 外层for循环控制循环次数
for(int j = 1;j <= a.length - 1;j++){//冒泡排序
// 内层for循环控制相邻的两个元素进行比较
for (int i = 0; i < a.length - j; i++) {
if (a[i] > a[i + 1]) {
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
直接选择排序
public class DirectSelectSort {
public static void sort(int[] array) {
//将数组的长度赋给len是为了防止每次for循环中判断时都调用length方法影响性能
int len = array.length;
for (int i = 0; i < len - 1; i++) {
int min = i;// 设当前第i条记录为最小值
// 找出(i+1)到(len-1)中最小值的下标
for (int j = i + 1; j < len; j++) {
if (array[j] < array[min]) {
min = j;// 记录最小值下标
}
}
// 将最小值记录与第i条记录交换
if (min != i) {
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
public static void main(String [] args){
int [] array = {45,89,699,52,14,236,58,7};
sort(array);
System.out.println(Arrays.toString(array));
}
}
直接插入排序
public class InsertSort {
public static void getInsertSort(int[] a) {
if(a == null || a.length == 0) {//判断数组是否为空
System.out.println("该数组为空！");
return;
}
int n = a.length;//将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能
int temp;//放于for循环外面是为了防止重复创建变量
int j;
for(int i = 1; i < n;i++){//排序的趟数
temp = a[i];//赋给temp是为了防止索引i之前的元素向后移动覆盖了索引i的元素
j = i-1;
for(j=i-1; j>=0&&a[j]>temp; --j) {//将大于i位置元素的元素向后移
a[j+1] = a[j];
}
a[j+1]= temp;//找到i应该在的位置，将值放置此处
}
}
public static void main(String[] args) {
int[] a = {3, 5, 1, 2, 6, 4, 7, 11, 23, 44, 3, 34};
getInsertSort(a);
for(int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
归并排序
归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。
工作原理：
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
package test;
import java.util.Arrays;
public class MergeSort {
/**
* 归并排序
* 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
* 时间复杂度为O(nlogn)
* 稳定排序方式
* @param nums 待排序数组
* @return 输出有序数组
*/
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 对左边数组进行递归
sort(nums, low, mid);
// 对右边数组进行递归
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];//定义新数组长度
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];//取出最小值放入左边的数组
} else {
temp[k++] = nums[j++];//取出最小值放入右边的数组
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
// 归并排序的实现
public static void main(String[] args) {
int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };
MergeSort.sort(nums, 0, nums.length-1);
System.out.println(Arrays.toString(nums));
}
}
快速排序
快速排序，顾名思义，是一种速度快，效率高的排序算法。
快排原理：
在要排的数（比如数组A）中选择一个中心值key（比如A[0]），通过一趟排序将数组A分成两部分，其中以key为中心，key右边都比key大，key左边的都key小，然后对这两部分分别重复这个过程，直到整个有序。
整个快排的过程就简化为了一趟排序的过程，然后递归调用就行了。
一趟排序的方法：
1，定义i=0，j=A.lenght-1，i为第一个数的下标，j为最后一个数下标
2，从数组的最后一个数Aj从右往左找，找到第一小于key的数，记为Aj；
3，从数组的第一个数Ai 从左往右找，找到第一个大于key的数，记为Ai；
4，交换Ai 和Aj
5，重复这个过程，直到 i=j
6，调整key的位置，把A[i] 和key交换
假设要排的数组为：A[8] ={ 5 2 8 9 2 3 4 9 }
选择 key = 5， 开始时 i=0，j=7
index 0 1 2 3 4 5 6 7
开始： 5 2 8 9 2 3 4 9
i j
第一次找 5 2 8 9 2 3 4 9
i j
交换： 5 2 4 9 2 3 8 9
i j
第二次找 5 2 4 9 2 3 8 9
i j
交换： 5 2 4 3 2 9 8 9
i j
第三次找 5 2 4 3 2 9 8 9
ij
调整key： 2 5 4 3 5 9 8 9
ij
package test;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] a = {1, 2, 4, 5, 7, 4, 5 ,3 ,9 ,0,88,55};
/*另一种输出方式
quickSort(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}*/
quickSort(a);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a) {
if(a.length>0) {
quickSort(a, 0 , a.length-1);
}
}
private static void quickSort(int[] a, int low, int high) {
//1,找到递归算法的出口
if( low > high) {
return;
}
//2, 存
int i = low;
int j = high;
//3,key
int key = a[ low ];
//4，完成一趟排序
while( i< j) {
//4.1 ，从右往左找到第一个小于key的数
while(i<j && a[j] > key){
j--;
}
// 4.2 从左往右找到第一个大于key的数
while( i<j && a[i] <= key) {
i++;
}
//4.3 交换
if(i<j) {
int p = a[i];
a[i] = a[j];
a[j] = p;
}
}
// 4.4，调整key的位置
int p = a[i];
a[i] = a[low];
a[low] = p;
//5, 对key左边的数快排
quickSort(a, low, i-1 );
//6, 对key右边的数快排
quickSort(a, i+1, high);
}
}
希尔排序
希尔排序(缩小增量法) 属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
h = 3 * h +1
反过来程序需要反向计算h序列，应该使用
h=(h-1)/3
package paixu;
import java.util.Arrays;
public class ShellSortTest {
public static void main(String[] args) {
int[] data = new int[] { 52, 13, 6, 22, 1, 9, 4, 8, 7,66,54 };
shellSort(data);
System.out.println(Arrays.toString(data));
}
public static void shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
}
}
// 计算出下一个h值
h = (h - 1) / 3;
}
}
}
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。（摘自百度百科）
想知道什么是堆排序，就得先知道什么是堆，堆分为两种，大根堆和小根堆，什么是大根堆小根堆呢？那你得先知道完全二叉树，什么是完全二叉树？完全二叉树，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。要是问什么是二叉树（自己去百度吧……），把完全二叉树理解了之后，就可以看大根堆小根堆了，大根堆的要求是每个节点的值都不大于其父节点的值，小根堆则相反，所以说，如果我构造出来一个大根堆，那么最上面的根节点一定是最大的
堆排序的原理就是这样，先构造出来大根堆（假设从小到大排序），然后取出堆顶元素（也就是最大的元素），放到数组的最后面，然后再将剩余的元素构造大根堆，再取出堆顶元素放到数组倒数第二个位置，依次类推，知道所有的元素都放到数组中，排序就完成了，仔细看代码吧，光看字是很难懂的
下面是Java代码实现：
public class HeapSortTest {
public static void main(String[] args)
{
//定义整型数组
int[] arr = {1,25,6,8,47,22,3,4,9,0};
//调用堆排序数组
HeapSort(arr);
//输出排序后的数组
System.out.println(Arrays.toString(arr));
}
//堆排序函数
public static void HeapSort(int[] arr)
{
int n = arr.length-1;
for(int i=(n-1)/2;i>=0;i--)
{
//构造大顶堆，从下往上构造
//i为最后一个根节点，n为数组最后一个元素的下标
HeapAdjust(arr,i,n);
}
for(int i=n;i>0;i--)
{
//把最大的数，也就是顶放到最后
//i每次减一，因为要放的位置每次都不是固定的
swap(arr,i);
//再构造大顶堆
HeapAdjust(arr,0,i-1);
}
}
//构造大顶堆函数，parent为父节点，last为数组最后一个元素的下标
public static void HeapAdjust(int[] arr,int parent,int last)
{
//定义临时变量存储父节点中的数据，防止被覆盖
int temp = arr[parent];
//2*parent+1是其左孩子节点
for(int i=parent*2+1;i<=last;i=i*2+1)
{
//如果左孩子大于右孩子，就让i指向右孩子
if(i<last && arr[i]<arr[i+1])
{
i++;
}
//如果父节点大于或者等于较大的孩子，那就退出循环
if(temp>=arr[i])
{
break;
}
//如果父节点小于孩子节点，那就把孩子节点放到父节点上
arr[parent] = arr[i];
//把孩子节点的下标赋值给parent
//让其继续循环以保证大根堆构造正确
parent = i;
}
//将刚刚的父节点中的数据赋值给新位置
arr[parent] = temp;
}
//定义swap函数
//功能：将根元素与最后位置的元素交换
//注意这里的最后是相对最后，是在变化的
public static void swap(int[] arr,int i)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
}