首先先上一个是十大排序算法对比图
image.png
1、冒泡排序（Bubble Sort）
算法流程:1、从头开始比较相邻的两个元素,如果第一个比第二个大,就交换他们的位置,执行完一轮后,就把最大的元素排到了最后一位
2、忽略最后一位，重新执行1，直到全部元素有序。
代码：
protected void sort() {
for (int end = array.length - 1; end > 0; end--) {
int sortedIndex = 1;
for (int begin = 1; begin <= end; begin++) {
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin-1);
sortedIndex = begin;
}
}
end = sortedIndex;
}
优化1,如果全部有序就提前结束循环
优化2,如果部分有序,后面那部分有序的前一个索引,减少交换遍历次数
2、选择排序（Selection Sort）
算法流程:
1、从序列中找出最大的那个元素，然后与最末尾的元素进行交换，执行完一轮后，最末尾的那个元素就是最大的元素
2、忽略1中找到的最大元素，重复执行1
private static void selectionSort(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
// 默认0号元素为最大值
int maxIndex = 0;
for (int begin = 1; begin <= end; begin++) {
// 为了保证排序的稳定性,要写>=
if (array[begin] >= array[maxIndex]) {
maxIndex = begin;
}
}
// 和最末尾的元素进行交换
int temp = array[maxIndex];
array[maxIndex] = array[end];
array[end] = temp;
}
System.out.println(Arrays.toString(array));
}
3、堆排序（Heap Sort）
堆排序可以认为是对选择排序的一种优化
算法流程:
1、对序列进行原地建堆（heapify）
2、重复执行以下操作,知道堆的元素数量为1
（1）交换堆顶元素与尾元素
（2）堆的元素数量减1
（3）对0位置进行一次siftDown操作
image.png
image.png
image.png
image.png
image.png
image.png
public class HeapSort extends Sort{
private int heapSize;
@Override
protected void sort() {
// 原地建堆
// 原地建堆
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
while(heapSize > 1) {
// 交换堆顶元素和尾部元素
swap(0,--heapSize);
// 对0位置进行siftDown,(恢复堆的性质)
siftDown(0);
}
//System.out.println(Arrays.toString(array));
}
private void siftDown(int index) {
Integer element = array[index];
int half = heapSize >> 1;
while (index < half) { // index必须是非叶子节点
// 默认是左边跟父节点比
int childIndex = (index << 1) + 1;
Integer child = array[childIndex];
int rightIndex = childIndex + 1;
// 右子节点比左子节点大
if (rightIndex < heapSize &&
cmpElement(array[rightIndex], child) > 0) {
child = array[childIndex = rightIndex];
}
// 大于等于子节点
if (cmpElement(element, child) >= 0) break;
array[index] = child;
index = childIndex;
}
array[index] = element;
}
}
4、插入排序(Inserttion Sort)
插入排序非常类似于扑克牌的排序
image.png
算法流程:
1、执行过程中会将序列分成两部分，前面的部分是排好序的，后面的部分是待排序的
2、从头到尾扫描每一个元素，每当扫到一个元素，就把他插入到合适的位置，使得前面的部分依然是排好序的
protected void sort() {
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
while (cur > 0 && cmp(cur, cur - 1) < 0) {
swap(cur, cur-1);
cur--;
}
}
//System.out.println(Arrays.toString(array));
}
插入排序优化1,将交换变为挪动
1、先将待插入的元素备份
2、头部有序数据中比待插入元素大，都朝尾部方向挪动一个位置
3、将待插入元素放到最终合适的位置
image.png
// 优化
protected void sort1() {
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
Integer v = array[cur];
while(cur > 0 && cmp(cur, cur - 1) < 0) {
array[cur] = array[cur - 1];
cur--;
}
array[cur] = v;
}
}
插入排序优化2
先来说一下二分搜索(Binary Search)
image.png
二分搜索思路:
1、假设在[begin,end}的范围内搜索一个元素v,先找到位置中点的元素mid=array[(begin+end)>>1;]
2、如果v大于mid,则排除前半部分,begin=midIndex+1,重复执行1
3、如果v小于mid,则排除半部分,end = midIndx,重复执行1
4、如果v等于mid,直接返回mid
image.png
image.png
image.png
public int indexOf(Integer[] array, int v) {
if (array == null || array.length == 0) {
return -1;
}
int begin = 0;
int end = array.length;
while(begin < end) {
int mid = (begin + end) >> 1;
if (array[mid] < v) {
begin = mid + 1;
} else if (array[mid] > v) {
end = mid;
} else {
return mid;
}
}
return -1;
}
插入查找优化代码
// 优化
protected void sort2() {
for (int begin = 1; begin < array.length; begin++) {
Integer element = array[begin];
int insertIndex = search(begin);
for (int i = begin ; i > insertIndex ; i--) {
array[i] = array[i -1];
}
array[insertIndex] = element;
}
}
private int search(int index) {
int v = array[index];
int begin = 0;
int end = index;
while (begin < end) {
int mid = (begin + end) >> 1;
if (v >= array[mid]) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}
5、归并排序
算法流程：
1、不断地将当前的序列平均分割成2个子序列
直到不能再分割（序列中只剩一个元素）
2、不断将2个子序列合并成一个有序序列
直到最终只剩下1个有序序列
图示
image.png
分割代码:
protected void sort() {
leftArray = new Integer[array.length >> 1];
sort(0, array.length);
System.out.println(Arrays.toString(array));
}
// T(n) = T(n/2) + T(n/2) + O(n)
/**
* 对 [begin, end) 范围的数据进行归并排序
*/
private void sort(int begin, int end) {
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin, mid);
sort(mid, end);
merge(begin, mid, end);
}
归并merge细节
image.png
image.png
image.png
image.png
image.png
代码:
package dierjisuanfa.sort;
import java.util.Arrays;
public class MergeSort extends Sort {
private Integer[] leftArray;
@Override
protected void sort() {
leftArray = new Integer[array.length >> 1];
sort(0, array.length);
System.out.println(Arrays.toString(array));
}
// T(n) = T(n/2) + T(n/2) + O(n)
/**
* 对 [begin, end) 范围的数据进行归并排序
*/
private void sort(int begin, int end) {
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin, mid);
sort(mid, end);
merge(begin, mid, end);
}
/**
* 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
*/
private void merge(int begin, int mid, int end) {
int li = 0, le = mid - begin;
int ri = mid, re = end;
int ai = begin;
// 备份左边数组
for (int i = li; i < le; i++) {
leftArray[i] = array[begin + i];
}
// 如果左边还没有结束
while (li < le) {
if (ri < re && array[ri]<leftArray[li]) {
array[ai++] = array[ri++];
} else {
array[ai++] = leftArray[li++];
}
}
}
}
6、快速排序
算法流程：
1、从序列中选择一个轴点元素（pivot）
假设每次选择0位置为轴点元素
2、利用pivot将序列分割成两个子序列
将小于pivot的元素放在pivot左侧
将大于pivot的元素放在pivot右侧
等于pivot的元素放在哪边都可以
3、对子序列进行1,2操作
直到不能再分割（子序列中只剩下1个元素）
图示
image.png
image.png
image.png
代码：
package dierjisuanfa.sort;
import java.util.Arrays;
/**
* 快速排序
* 1.从序列中选择一个轴点元素
* 假设每次选择0位置的元素为轴点元素
*
* 2.利用pivot将序列分割为2个子序列
* 将小于pivot的元素放在pivot前面(左侧)
* 将大于pivot的元素放在pivot后面(右侧)
* 3.对子序列进行1,2操作
* 直到不能再分割(子序列只剩一个元素)
*
* 快速排序的本质
* 逐渐将每一个元素都转换成轴点元素
*/
public class QuickSort extends Sort{
@Override
protected void sort() {
sort(0, array.length);
System.out.println(Arrays.toString(array));
}
/**
* 对[begin, end)范围的元素进行快速排序
* @param beign
* @param end
*/
private void sort(int beign, int end){
if(end - beign < 2) {
return;
}
// 确定轴点位置
int mid = pivotIndex(beign, end);
// 对子序列也进行快速排序
sort(beign, mid);
sort(mid + 1, end);
}
/**
* 确定[begin,end)范围的轴点元素
* @param beign
* @param end
* @return 轴点元素的最终位置
*/
private int pivotIndex(int beign, int end) {
// 随机选择一个元素跟begin位置进行交换
swap(beign,beign + (int)(Math.random()*(end-beign)));
// 备份begin位置的元素
Integer pivot = array[beign];
end--;
while(beign < end) {
while(beign < end) {
// 从右往左扫描
if(cmpElement(pivot,array[end]) < 0) {// 右边元素 > 轴点元素
end--;
} else {
array[beign] = array[end];
beign++;
break;
}
}
while(beign < end) {
// 从左往右扫描
if (cmpElement(pivot, array[beign]) > 0) {
beign++;
} else {
array[end] = array[beign];
end--;
break;
}
}
}
// 将轴点元素放入最终位置
array[beign] = pivot;
// 返回轴点元素的位置
return beign;
}
}
7、希尔排序
希尔排序把序列看作是一个矩阵，分为m列，逐列进行排序
m从某个整数逐渐减为1
当m为1是，整个序列将完全有序
希尔排序也被称为递减增量排序
矩阵的列数取决于步长序列
比如，如果步长序列为{1,5,19,41,109},就代表依次分为109列,41列,19列,5列,1列进行排序
不同的步长序列,执行效率也不同
image.png
image.png
image.png
image.png
image.png
代码:
@Override
protected void sort() {
List<Integer> stepSequence = shellStepSequence();
System.out.println(stepSequence);
for (Integer step : stepSequence) {
sort(step);
}
System.out.println(Arrays.toString(array));
}
private void sort(int step) {
// col:第几列,column的简称
for (int col = 0; col < step; col++) {
// 对[0,array.length)排序
for (int begin = col+step; begin < array.length; begin+=step) {
int cur = begin;
while (cur > col && cmp(cur, cur - step) < 0) {
swap(cur, cur-step);
cur-=step;
}
}
}
}
private List<Integer> shellStepSequence() {
List<Integer> stepSequence = new ArrayList<>();
int step = array.length;
while((step >>= 1) > 0) {
stepSequence.add(step);
}
return stepSequence;
}
