当n较大时，则应采用时间复杂度为O(nlogn)的排序算法：快速排序、堆排序、归并排序。
常见的排序算法有：
- 插入排序（直接插入、希尔排序）
- 选择排序（简单选择、堆排序）
- 交换排序（冒泡排序、快速排序）
- 归并排序
当n较大时，则应选择时间复杂度为O(nlogn)的排序算法：快速排序、堆排序、归并排序
快速排序是目前基于比较的内部排序中被认为最好的方法，当待排的关键字是随机分布时，快速排序的平均时间最短
如果大体有序的话，可以选择插入排序。
插入排序：
public static void insertSort(int[] arr){
//存放待插入元素
int temp;
for (int i = 1; i < arr.length; i++){
temp = arr[i];
int j;
for (j = i - 1; j >= 0; j--){
//如果符合条件就往后移位，为当前元素腾出空间
if (arr[j] > temp){
arr[j + 1] = arr[i];
} else {
break;
}
}
arr[j + 1] = temp;
}
}
希尔排序：
基于插入排序的思想，缩小增量排序（直接插入的改进版）
public static void shellSort(int[] arr){
//获取数组长度，确定增量gap
int len = arr.length;
int gap = len / 2;
int tmp;
while(gap > 0){
for(int i = gap; i < len; i++){
tmp = arr[i];
//获取前一个元素的索引
int preIndex = i - gap;
while(preIndex >= 0 && arr[preIndex] > tmp){
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = tmp;
}
gap /= 2;
}
}
选择排序：
public static void selectSrot(int[] arr){
int tmp;
for(int i = 0; i < arr.length; i++){
for(int j = j + 1; j < arr.length; j++){
if (arr[i] > arr[j]){
swap;
}
}
}
}
堆排序：
借助完全二叉树进行排序，将数据构建成大根堆或者小根堆，然后将顶点的元素和最后的元素互换，然后继续构建大根堆的过程。
设一个节点为R[i]，则左孩子节点为R[2 * i + 1]，右孩子为R[2 * i + 2]
最后一个非叶子节点为R[(len - 1) / 2]
public static void heapSort(int[] arr){
//循环建立初始堆
for(int i = (arr.length - 1) / 2; i >= 0; i--){
headAdjust(arr, i, arr.length);
}
//进行n - 1次循环，完成排序
for(int i = arr.length - 1; i--){
//最后一个元素和第一个元素交换
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
//然后将将除最后一个元素继续构建大根堆
headAdjust(arr, 0, i);
}
}
public static void headAdjust(int[] arr, int parent; int len){
//保存当前父节点
int tmp = arr[parent];
int child = parent * 2 + 1;
while(child < len){
//判断是否有右孩子，并且右孩子的值大于左孩子的值，则选择右孩子
if (child + 1 < len && arr[child] < arr[child + 1]){
child++;
}
//如果父节点的值大于孩子节点的值，则直接退出
if (tmp >= arr[child]){
break;
}
//把孩子节点的值赋值给父节点
arr[parent] = arr[child];
arr[child] = tmp;
}
}
冒泡排序：
public static void bubbleSort(int[] arr){
int tmp;
for(int i = 1; i < arr.length; i++){
for(int j = 0; j <= arr.length - 1 - i; j++){
if (arr[j] > arr[j + 1]){
swap;
}
}
}
}
快速排序：
选取第一个元素作为基准元素，两端各设两个哨兵，右边移动到小于基准元素时停止，左边开始移动，直至遇到大于基准元素时停止，然后两元素交换，重复次过程，直至两哨兵相遇，将基准元素和相遇的值进行交换，此时基准元素左边的元素均小于基准元素，基准元素右边的值均大于基准元素，然后将基准元素左右两端的元素重复此过程，直至完全有序。
public static void quickSort(int left, int right){
int i, j, t, tmp;
if(left > right){
return;
}
//基准元素
tmp = arr[left];
//左哨兵
i = left;
//右哨兵
j = right;
//顺序很重要，要先从左边开始
while(i != j){
while(arr[j] > tmp && i > j){
j--;
}
while(arr[i] < tmp && i > j){
i++;
}
if(i < j){
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
//最终将基准元素归位
arr[left] = arr[i];
arr[i] = tmp;
quickSort(left, i - 1);
quickSort(i + 1, right);
}
归并排序：
public static void mergeSort(int[] arr, int left, int right){
int mid = (right + left) / 2;
if (left < right){
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right){
//创建一个临时数组用于存放排序的数据
int[] tmp = new int[right - left + 1];
int i = left; //左指针
int j = mid + 1; //右指针
int k = 0;
//将小的元素添加到临时数组中
while(i < mid && j < right){
if (arr[i] < arr[j]){
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
//将左边或右边剩余的元素添加到临时数组中
while(i <= mid){
tmp[k++] = arr[i++];
}
while(j <= right){
tmp[k++] = arr[j++];
}
//将临时数组添加到原数组中
k = 0;
while(left <= right){
arr[left++] = tmp[k++];
}
}
网友评论