排序算法
归并排序
// 归并排序
public static void mergeSort(int[] arr){
// 创建一个临时数组，用来存储合并之后的数组
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] a, int[] b, int left, int right){
// 当left==right的时，已经不需要再划分了
if (left < right){
int middle = (left+right)/2;
internalMergeSort(a, b, left, middle); //左子数组
internalMergeSort(a, b, middle+1, right); //右子数组
mergeSortedArray(a, b, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
// 这里的核心就是合并两个有序数组，谁大放进新的数组
while (i <= middle && j <= right){
if (arr[i] <= arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
// 左边的还有剩余
while (i <= middle){
temp[k++] = arr[i++];
}
// 右边的还有剩余
while (j <= right){
temp[k++] = arr[j++];
}
// 把数据复制回原数组
for (i=0; i希尔排序又称缩小增量排序
public static void shellSort(int[] arr){
int temp;
for (int delta = arr.length/2; delta>=1; delta/=2){ //对每个增量进行一次排序
for (int i=delta; i=delta && arr[j] 堆排序
- 如何初始化一个堆
- 排序过程中如何去调整堆
- 堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。
-
适用于解决前 n 大的算法
public class HeapSort { //对data数组从0到lastIndex建大顶堆 public static void buildMaxHeap(int[] data, int lastIndex){ //从lastIndex处节点（最后一个节点）的父节点开始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在，lastIndex 是最后一个节点的索引，不是其父节点的索引，要注意 while(k2+1<=lastIndex){ //k节点的左子节点的索引 int biggerIndex=2k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 if(biggerIndex}
选择排序
设现在要给数组arr[]排序，它有n个元素。
- 对第一个元素（Java中，下标为0）和第二个元素进行比较，如果前者大于后者，那么它一定不是最小的，但是我们并不像冒泡排序一样急着交换。我们可以设置一个临时变量a，存储这个目前最小的元素的下标。然后我们把这个目前最小的元素继续和第三个元素做比较，如果它仍不是最小的，那么，我们再修改a的值。如此直到和最后一个元素比较完，可以肯定a存储的一定是最小的元素的下标。
- 如果a的值不为0（初始值，即第一个元素的下标），交换下标为a和0的两个元素。
- 重复上述过程，这次从下标为1的元素开始比较，因为下标为0的位置已经放好了最小的元素了。
-
如此直到只剩下最后一个元素，可以肯定这个元素就是最大的了。
public static void selectionSort(int[] arr) { int temp, min = 0; for (int index = 0; index < arr.length - 1; ++index) { min = index; // 循环查找最小值 for (int j = index + 1; j < arr.length; ++j) { // 如果比当前的小，就交换，不是的话就算了，继续 if (arr[min] > arr[j]) { min = j; } } // 把最小的与 index 位置元素交换 if (min != index) { temp = arr[index]; arr[index] = arr[min]; arr[min] = temp; } } }
冒泡排序
设现在要给数组arr[]排序，它有n个元素。
1.如果n=1：显然不用排了。
2.如果n>1：
1)我们从第一个元素开始，把每两个相邻元素进行比较，如果前面的元素比后面的大，那么在最后的结果里面前者肯定排在后面。所以，我们把这两个元素交换。然后进行下两个相邻的元素的比较。如此直到最后一对元素比较完毕，则第一轮排序完成。可以肯定，最后一个元素一定是数组中最大的（因为每次都把相对大的放到后面了）。
2)重复上述过程，这次我们无需考虑最后一个，因为它已经排好了。
3)如此直到只剩一个元素，这个元素一定是最小的，那么我们的排序可以结束了。显然，进行了n-1次排序。
上述过程中，每次（或者叫做“轮”）排序都会有一个数从某个位置慢慢“浮动”到最终的位置（画个示意图，把数组画成竖直的就可以看出来），就像冒泡一样，所以，它被称为“冒泡排序法”。
public static void bubbleSort(int[] arr) {
int temp = 0;
for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}//loop j
}//loop i
}// method bubbleSort快速排序
- 快排的思想很简单，从左到右依次往中间前进
-
复杂度要记住为 O(n logn)
public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1); } private static void qsort(int[] arr, int low, int high){ if (low < high){ int pivot=partition(arr, low, high); //将数组分为两部分 qsort(arr, low, pivot-1); //递归排序左子数组 qsort(arr, pivot+1, high); //递归排序右子数组 } } private static int partition(int[] arr, int low, int high){ int pivot = arr[low]; //枢轴记录 while(low
插入排序
- 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
- 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
- 重复上述过程直到最后一个元素被插入有序子数组中。
-
排序完成。
public static void insertionSort(int[] arr){ // 注意 i = 1 开始排序的，即从第二个元素开始 for (int i=1; i