1，快速排序
快速排序原理是首先要找到一个中枢，把小于中枢的值放到他前面，大于中枢的值放到他的右边，然后再以此方法对这两部分数据分别进行快速排序。先看一下代码
public int[] MySort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
return arr;
}
private void quickSort(int[] array, int start, int end) {
if (start < end) {
int key = array[start];//用待排数组的第一个作为中枢
int i = start;
for (int j = start + 1; j <= end; j++) {
if (key > array[j]) {
swap(array, j, ++i);
}
}
array[start] = array[i];//先挪，然后再把中枢放到指定位置
array[i] = key;
quickSort(array, start, i - 1);
quickSort(array, i + 1, end);
}
}
//交换两个数的值
public void swap(int[] A, int i, int j) {
if (i != j) {
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
}
} 这里是先用待排数组的第一个作为中枢，把数组划分两部分，小于他的往前挪，那大于他的自然就在后面了，然后再把中枢值放到大于和小于他之间的位置。
快速排序其实有很多变种，这里就不在一一看了，想了解的可以看下《104，排序-快速排序》
2，归并排序
归并排序是把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
代码如下
public int[] MySort(int[] arr) {
int i = 1;
while (i < arr.length) {
//原理很简单，就是先两个两个合并，然后4个，然后8个……
for (int j = 0; j + i < arr.length; j += 2 * i) {
merge(arr, j, j + i - 1, Math.min(j + 2 * i - 1, arr.length - 1));
}
i = i << 1;
}
return arr;
}
private void merge(int[] data, int left, int center, int right) {
int length = right - left + 1;
int[] tmp = new int[length];
int tempIndex = 0;
//_left是前半部分开始的位置，_right是后半部分开始的位置
int _left = left;
int _right = center + 1;
while (_left <= center && _right <= right) {
if (data[_left] <= data[_right]) {
tmp[tempIndex++] = data[_left++];
} else {
tmp[tempIndex++] = data[_right++];
}
}
while (_right <= right) {
tmp[tempIndex++] = data[_right++];
}
while (_left <= center) {
tmp[tempIndex++] = data[_left++];
}
tempIndex = 0;
while (tempIndex < length) {
data[left + tempIndex] = tmp[tempIndex++];
}
} 3，堆排序
堆排序，也可以理解为二叉树排序，这里的堆分为两种，一种是大顶堆，一种是小顶堆，我们所有的排序方法都以升序为主，其实倒序原理也都差不多，所以这里我们主要分析的是大顶堆。大顶堆就是根节点不小于他的两个子节点，
代码如下
public int[] MySort(int[] arr) {
int length = arr.length;
buildMaxHeap(arr, length);
for (int i = 0; i < length; i++) {
swap(arr, 0, length - 1 - i);
maxHeapfy(arr, 0, length - i - 1);
}
return arr;
}
private void maxHeapfy(int[] arr, int i, int heapSize) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {//把最大值给父节点
swap(arr, largest, i);
maxHeapfy(arr, largest, heapSize);
}
}
private void buildMaxHeap(int[] array, int heapSize) {
//从最后一个非叶子节点开始循环
for (int i = (heapSize - 2) >> 1; i >= 0; i--) {
maxHeapfy(array, i, heapSize);
}
}
public void swap(int[] A, int i, int j) {
if (i != j) {
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
}
} 排序的方式太多了，这里就不在一一列举了，如果想了解更多，可以看下
《101，排序-冒泡排序》
《102，排序-选择排序》
《103，排序-插入排序》
《104，排序-快速排序》
《105，排序-归并排序》
《106，排序-堆排序》
《107，排序-桶排序》
《108，排序-基数排序》
《109，排序-希尔排序》
《110，排序-计数排序》
《111，排序-位图排序》
《112，排序-其他排序》
我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号