一、时间复杂度为O(n^2)的排序（冒泡排序、选择排序、插入排序）
1.冒泡排序
快速回忆过程：
1.选择区间[0 ~ n-1],遍历，每次与下一个元素比较，若大于下一个元素，则交换。一轮遍历过后，确保当前子数组的最大元素为最后一个元素。
2.依次选择区间[0 ~ n-2]...[0 ~ 1]，执行step1即可。
import java.util.*;
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
// 双重循环实现
for(int i = 0; i < n-1; i++){
for(int j = 0; j < n-i-1; j++){
if(A[j] > A[j+1]){
swap(A, j , j+1);
}
}
}
return A;
}
private void swap(int[] array, int index1, int index2){
//交换数组index1和index2位置的元素
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}2.选择排序
快速回忆过程：
1.选择区间[0 ~ n-1],遍历，每次找出该区间的最小元素放在该区间的第一个位置。一轮遍历过后，确保当前子数组的最小元素为第一个元素。
2.依次选择区间[1 ~ n-1]...[n-2 ~ n-1]，执行step1即可。
import java.util.*;
public class SelectionSort {
public int[] selectionSort(int[] A, int n) {
// write code here
int currentMin; //当前遍历区间的最小值
int currentMinIndex; //当前遍历区间最小值的索引
for(int i = 0; i < n-1; i++){
//每次遍历区间前，将第一个元素暂视为最小元素
currentMin = A[i];
currentMinIndex = i;
for(int j = i+1; j < n; j++){
if(currentMin > A[j]){
currentMin = A[j];
currentMinIndex = j;
}
}
swap(A, i, currentMinIndex); //区间遍历完成后，交换最小元素和区间的第一个元素
}
return A;
}
private void swap(int[] A, int index1, int index2){
int temp = A[index1];
A[index1] = A[index2];
A[index2] = temp;
}
}3.插入排序
快速回忆过程：
1.选择元素array[1]，与array[0]比较，若array[1]更小，则与array[0]交换。
2.一般过程：选择元素array[n]，与array[n-1]比较，若array[n]更小，则交换,然后让array[n-1]再与array[n-2]比较，依次类推，直到遍历到array[0]或比较中出现大于关系array[i]>array[i-1]。（也就是说，一次遍历后，子区间一定是递增的）
import java.util.*;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
// write code here
int insertIndex; //最终插入的索引
int temp; //暂存当前区间最后一个元素，最终插入到insertIndex的位置。
for(int i = 1; i < n; i++){
//初始化
insertIndex = i;
temp = A[i];
for(int j = i-1; j>=0; j--){
if(temp < A[j]){
A[j+1] = A[j]; //向后移动元素
insertIndex = j; //记录插入位置
}
else{
break;
}
}
A[insertIndex] = temp; //插入
}
return A;
}
}二、时间复杂度为O(n*log n)的排序（归并排序，快速排序，堆排序、希尔排序）
1.归并排序
快速回忆过程：
1.将每个元素变为单独的有序区间，然后依次两两归并成新的有序区间即可。
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
// 元素个数小于等于1，返回
if(n <= 1 || A == null)
return A;
int left; //用于记录当前归并集的第一个数组的第一个元素的位置
int mid; //用于记录当前归并集的第二个数组的第一个元素的位置
int right; //用于记录当前归并集的第二个数组的最后一个元素的位置
for(int interval = 1; interval < n; interval = interval*2){ //每轮归并后，归并集大小提升2倍。
//根据当前归并集大小初始化
left = 0;
mid = interval;
right = 2*interval-1;
while(true){
/*这里一共有三种情况：
【1】mid>n-1，说明数组剩余元素数只够一个归并集，那么不用归并，并跳出循环，开始下一轮归并。
【2】mid<=n-1 && right>=n-1，说明数组剩余元素数不能填满第二个归并集，那么进行最后一次归并，并跳出循环，开始下一轮归并。
【3】mid<=n-1 && right<n-1，说明数组剩余元素数完全够2个归并集，那么归并，并进行本轮下一次归并。
*/
if(mid > n-1) break;
if(mid <= n-1 && right >= n-1){
merge(A, left, mid, n-1);
break;
}
else{
merge(A, left, mid, right);
left = left + 2*interval;
mid = mid + 2*interval;
right = right + 2*interval;
}
}
}
return A;
}
private void merge(int[] A, int left, int mid, int right){
//归并函数，相当于已知两个有序数组求它们合并后的有序数组。
int[] temp = new int[right - left + 1];
int i = left;
int j = mid;
int index = 0;
while(i <= mid-1 && j <= right){
if(A[i] <= A[j])
temp[index++] = A[i++];
else
temp[index++] = A[j++];
}
while(i <= mid-1)
temp[index++] = A[i++];
while(j <= right)
temp[index++] = A[j++];
index = left;
for(int element : temp)
A[index++] = element;
}
}2.快速排序
快速回忆过程：
1.随机选择一个元素，进行依次Patition过程，使得它左边的元素小于它，右边的元素大于它。
2.对左右区间递归调用快速排序即可。
Patition过程：
【1】先将划分元素与最后一个元素交换，并定义一个小于等于区间，表示小于等于划分值的区间，初始时长度为0
【2】从左到右遍历所有元素，若大于划分值，则继续遍历，若小于等于划分值，则将小于等于区间长度位置元素与当前位置元素交换，并且小于等于区间向右扩一个位置（例如小于等于区间为空，并且array[5] < 划分值，则array[5]与array[0]交换。小于等于区间变为{array[0]}）
【3】遍历完成后，将划分值与小于等于区间的下一个元素交换。
import java.util.*;
public class QuickSort {
public int[] quickSort(int[] A, int n) {
// write code here
if(A == null || n < 2)
return A;
process(A, 0, n-1); //开始排序
return A;
}
private void process(int[] A, int left, int right){
if(left >= right)
return;
int randomIndex = left + (int)(Math.random()*(right - left +1)); //随机划分位置
int mid = patition(A, randomIndex, left, right); //进行一次划分过程，并生成最终划分值的位置
process(A, left, mid-1); //向左递归调用
process(A, mid+1, right); //向右递归调用
}
private int patition(int[] A, int randomIndex, int left, int right){
swap(A, randomIndex, right); //先交换划分值和最后一个元素
int lessEqualSection = left; //指定小于等于区间的下一个位置
for(int i = left; i < right; i++){
if(A[i] <= A[right]){ //元素小于划分值，则小于等于区间下一个位置元素与当前元素交换，小于等于区间增加1
swap(A, lessEqualSection++, i);
}
}
swap(A, lessEqualSection, right); //最终的小于等于区间下一个元素与划分值交换
return lessEqualSection; //返回小于等于区间的下一个元素的位置，即划分值的位置
}
private void swap(int[] A, int index1, int index2){
int temp = A[index1];
A[index1] = A[index2];
A[index2] = temp;
}
}3.堆排序
快速回忆过程：
1.构建大根堆。
2.将大根堆的堆顶元素与最后一个元素交换并将最后一个元素移出堆，作为结果数组的最后一个元素。
3.重新调整堆为大根堆
4.重复step1-3，直到堆中只剩一个元素为止
import java.util.*;
public class HeapSort {
public int[] heapSort(int[] A, int n) {
// write code here
if(A == null)
return A;
for(int i = n/2-1; i >= 0; i--){ //建立大顶堆
adjustHeap(A, i, n);
}
for(int i = n-1; i > 0; i--){ //堆排序过程
swap(A, 0, i); //交换首尾元素
adjustHeap(A, 0, i); //重新调整堆为大顶堆
}
return A;
}
private void adjustHeap(int[] A, int current, int length){
int temp = A[current]; //记录堆顶元素最后赋值，可以减少交换次数
for(int i = 2*current+1; i < length; i = i*2+1){ //从当前节点开始向下调整
if(i+1 < length && A[i+1] > A[i]){ //右孩子大于左孩子，则改为比较右孩子
i++;
}
if(A[i] > temp){ //如果父节点小于子节点，则交换（这里赋值，最后再交换，因此每次用temp比较）
A[current] = A[i];
current = i;
}
else{ //如果父节点大于子节点，则不用调整，退出循环
break;
}
}
A[current] = temp;
}
private void swap(int A[], int index1, int index2){
int temp = A[index1];
A[index1] = A[index2];
A[index2] = temp;
}
}4.希尔排序
快速回忆过程：
希尔排序相当于插入排序的一般化，插入排序的步长为1，而希尔排序的步长逐渐由大到小最后变为1。
希尔排序的时间复杂度是不确定的，当选择合适的步长时，最优可以达到O(n*log n)，最差则为O(n^2)。
import java.util.*;
public class ShellSort {
public int[] shellSort(int[] A, int n) {
// write code here
if(A == null || n < 2)
return A;
int temp;
int index;
for(int feet = n/2; feet > 0; feet/=2){ //初始步长为长度的一般，步长不断除以2
for(int i = feet; i < n; i++){ //执行一次插入排序
temp = A[i]; //保存待插入的元素，可以避免交换
index = i; //插入位置
while(index - feet >= 0){
if(temp < A[index - feet]){
A[index] = A[index - feet];
index -= feet;
}
else
break;
}
A[index] = temp;
}
}
return A;
}
}
京公网安备 11010502036488号