排序分类.png
性能比较
对比图.png
O(nlogn)效率优于O(n^2)
简单算法：冒泡、选择、直接插入
改进算法：希尔、堆、快速、归并
不稳定的排序----快些选队（快速排序、希尔排序、选择排序、堆排序）
冒泡排序
public static void BubbleSort(int[] num) {
int size =num.length;
boolean flag = false;
for(int i = 0; i< size-1; i++) {
for(int j = 0; j< size-1-i; j++) {
if (num[j] > num[j+1]) {
int temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
flag = true;
}
}
if (flag == false) {
break; //遍历一遍数组后发现无元素交换时说明此时数组已有序
}
}
}
快速排序（冒泡排序的升级，同属于交换排序类）
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
适用于数据量较大的情况
原始算法
public static void quickSort(int[] num,int low, int high) {
if (low < high) {
int middle = getMiddle(num, low, high); //将数组一分为二
quickSort(num, low, middle-1); //对低字段进行递归排序
quickSort(num, middle+1, high); //对高字段进行递归排序
}
}
public static int getMiddle(int[] num, int low, int high) {
int temp = num[low]; //优化前：选取第一个字段作为基准值
while(low < high) {
while(low < high && num[high] > temp) { //从后往前找到一个比基准值小的数
high--;
}
swap(num, low, high);
while(low <high && num[low] < temp) { //从前往后找一个比基准值大的数
low++;
}
swap(num, low, high);
}
return low; //返回中轴所在位置
}
public static void swap(int[] num, int low, int high) {
int temp = num[low];
num[low] = num[high];
num[high] = temp;
}
优化算法
采用三数取中方式选取基准值
采用替换方式而不是交换方式进行操作
public static int getMiddle(int[] num, int low, int high) {
//快速排序优化：三数取中方式选取基准值
int m = low + (high - low) /2; //获取数组中间值下标
if (num[low] > num[high]) {
swap(num, low, high); //保证左端小于右端
}
if (num[m] > num[high]) {
swap(num, m, high); //保证中间小于右端
}
if (num[m] > num[low]) {
swap(num, m, low); //保证左端小于中间
}
int temp = num[low]; //优化后：选取数组第一个数，中间的数以及最后一个数中的中间数最为基准值
while(low < high) { //循环结束后low和high指向同一元素，该元素的位置就是基准元素的位置
while(low < high && num[high] > temp) { //从后往前找到一个比基准值小的数
high--;
}
num[low] = num[high]; //采用替换而不是交换方式进行操作
while(low <high && num[low] < temp) { //从前往后找一个比基准值大的数
low++;
}
num[high] = num[low];
}
num[low] = temp; //将保存的基准值替换到相应位置
return low; //返回中轴所在位置
}
选择排序
思想：在待排序的数中，选出一个最小的数与第一个位置的数交换，然后在剩下的数中找到第二小的数与第二个位置的数交换，如此反复。
public static void selectSort(int[] num) {
for(int i = 0; i < num.length; i++) {
int min = i;
for(int j = i+1; j < num.length; j++){
if (num[j] < num[min]) {
min = j;
}
}
if (i != min) {
swap(num,i,min);
}
}
}
优化思路：每次遍历都找出一个最大值以及最小值
堆排序（选择排序的升级）
思路：构造一个最大堆，将根结点的值与最后一个叶节点交换，然后排除该叶节点后再次构造最大堆。
for(int i=0; i<num.length-1; i++) {
//循环建立最大堆
buildMaxHeap(num, num.length-1-i);
//交换根节点和最大堆最后一个叶节点
swap(num, 0, num.length-1-i);
}
public static void buildMaxHeap(int[] num, int lastIndex) {
//从lastIndex节点的父节点开始循环
for(int i = (lastIndex-1) /2; i>=0; i--) {
//保存正在判断的节点
int temp = i;
//当前节点的子节点存在时
while( temp*2+1 <= lastIndex) {
//当前节点的左节点
int biggerIndex = 2*temp+1;
if (biggerIndex < lastIndex) {
//biggerIndex指向当前节点左右孩子节点中较大值的索引
if (num[biggerIndex] < num[biggerIndex+1]) {
biggerIndex++;
}
}
//当前节点小于子女节点中较大值时
if (num[temp] < num[biggerIndex]) {
//交换位置
swap(num,temp,biggerIndex);
//开启while的下一次循环，保证temp节点的值大于左右孩子节点的值
temp = biggerIndex;
}else {
break;
}
}
}
}
直接插入排序
思路：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数加1的有序表。
public static void insertSort(int[] num) {
int i,j;
for( i = 0; i< num.length; i++) {
int temp = num[i];
for( j = i; j > 0 && temp < num[j-1]; j-- ) {
//temp小于前面的值，则前面的数右移
num[j] = num[j-1];
}
num[j] = temp;
}
}
希尔排序（直接插入排序升级版）
思路：将待排序的数组按一定步长进行分组，并在每个分组中应用直接插入排序算法，然后缩短步长再次进行分组，直到步长为0为止。
public static void shellSort(int[] num) {
//设置步长
int step = num.length/2;
while(step >= 1) {
for(int i = step; i< num.length; i+=step) {
int temp = num[i];
int j;
//直接插入排序算法
for(j=i; j>0 && num[j-step] > temp; j-=step) {
num[j] = num[j-step];
}
num[j] = temp;
}
//缩小步长直到step为0
step = step/2;
}
}
归并排序
思路：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2(向上取整)个长度为2或1的有序序列，再两两归并......,如此反复，直至得到一个长度为n的有序序列为止，这种排序称为2路归并排序。
/**
* @param num 待排序数组
* @param n 排序元素个数
*/
public static void mergerSort(int[] num, int n) {
sort(num, 0, n-1);
}
public static void sort(int[] num, int left, int right) {
if (left < right) {
int middle = (right + left)/2;
sort(num, left, middle);
sort(num, middle+1, right);
merge(num, left, middle, right);
}
}
public static void merge(int[] num, int left, int mid, int right) {
//计算数组大小
int n = right-left+1;
//创建临时数组保存数据
int[] tempArr = new int[n];
//临时数组下标
int t = 0;
int r = mid+1;
int l = left;
while(l <= mid && r <= right) {
if (num[l] < num[r]) {
tempArr[t++] = num[l++];
}else {
tempArr[t++] = num[r++];
}
}
//剩余元素加入临时数组
while(l <= mid) {
tempArr[t++] = num[l++];
}
while(r <= right) {
tempArr[t++] = num[r++];
}
//将临时数组的值复制到原数组中
for(int i = 0; i < t ; i++) {
num[left+i] = tempArr[i];
}
}
