目录
1.排序的理解+10种排序比较
定义：是一个序列对象按照某个关键字进行递增或递减的操作
几个关键词理解：
（1）稳定性：如果a原本在b前面，并且a=b，排序之后a仍然在b的前面，说明这个是稳定的，反之，就不稳定。
（2）内部排序：数据元素全部放在内存中的排序。
（3）外部排序：数据元素太多不能同时放在内存中，所以把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
一个稳定的排序，可以变成不稳定的排序
一个不稳定的排序，不可以变成稳定的排序
（4）10中排序比较
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n^1.3) | O(n^1.3) | O(n^1.5) | O(1) | 不稳定 |
| 堆排序 | O(n*logn) | O(n*logn) | O(n*logn) | O(1) | 不稳定 |
| 快速排序 | O(n*logn) | O(n*logn) | O(n^2) | O(logn)~O(n) | 不稳定 |
| 归并排序 | O(n*logn) | O(n*logn) | O(n*logn) | O(n) | 稳定 |
| 计数排序 | O(MAX(n,范围)) | O(MAX(n,范围)) | O(MAX(n,范围)) | O(范围) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
| 桶排序 | O(n) | O(n+k) | O(n^2) | O(n+k) | 基于桶内比较算法 |
2.直接插入排序（有序使用最好）
基本思想：将未排序的数据元素，在已经排好的有序序列中从后向前扫描，找到对应位置然后插入
在扫描的过程中，需要反复把已经排序的元素向后挪动，为准备新插入的元素提供空间
* 直接插入排序
* 时间复杂度：
* 最坏：O(n^2) 数据元素全部逆序时
* 最好：O(n) 数据元素全部有序时
* 空间复杂度：O(1)
* 稳定性：稳定
* 数据元素基本上有序时，使用效果最好
实现步骤：比如
上代码：
public void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= 0; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入 位置需比较
(C)
次？（采用从后往前比较）A: 3 B: 4 C: 5 D:6
3.希尔排序（缩小增量算法）
基本思想：希尔排序是选的一个增量值分组，然后对每组使用直接插入排序算法排序，随着增量值减小，每组包含的值也越来越多，当增量值减为1时，整个序列在一组内排序
* 希尔排序
* 时间复杂度：O(n^1.3 - n^1.5)
* 空间复杂度：O(1)
* 稳定性：不稳定
实现步骤：
private static void shell(int[] array,int gap) {
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0; j-=gap) {
if(array[j] > tmp) {
array[j+gap] = array[j];
}else {
break;
}
}
array[j+gap] = tmp;
}
}
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
shell(array,gap);
gap /= 2;
}
shell(array,1);
}下列排序法中，最坏情况下时间复杂度最小的是
（A）A: 堆排序 B: 快速排序 C: 希尔排序 D: 冒泡排序O(n*logn) O(n*2) O(n^1.5) O(n^2)
4.直接选择排序
基本思想：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
* 直接选择排序
* 数据复杂度：O(n^2) （对数据不敏感，不管数据有序还是无序都是这样）
* 空间复杂度：O(1)
* 稳定性：不稳定
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
//每次将i下标的值当做最小值
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array,minIndex,i);
}
}
private static void swap(int[] array,int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}（2）前面是用了一个minIndex去找最小值然后交换，最后排序
那么如果用两个一个minIndex去找最小值，一个maxIndex去找最大值，
然后用left指向前，right指向后，
比如说是升序那就minIndex和left交换，
maxIndex和right交换，这样效率应该是比第一种方法要快
public static void selectSort2(int[] array) {
int left = 0;
int right = array.length-1;
while(left < right) {
int minIndex = left;
int maxIndex = left;
for(int i = left+1; i <= right; i++) {
if (array[i] < array[minIndex]) {
minIndex = i;
}
if (array[i] > array[maxIndex]) {
maxIndex = i;
}
}
swap(array,left,minIndex);
//修正maxIndex下标
if(left == maxIndex) {
maxIndex = minIndex;
}
swap(array,right,maxIndex);
left++;
right--;
}
}5.堆排序
基本思想：堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
不了解堆的可以看一下，我的另一篇博客，里面有很好的介绍
数据结构之【堆】（Heap）
http://t.csdn.cn/H0i2R
* 堆排序
* 时间复杂度：O(n*logn)
* 空间复杂度：O(1)
* 稳定性：不稳定
public static void heapSort(int[] array) {
createBigHeap(array);
int end = array.length-1;
while(end >= 0) {
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
private static void createBigHeap(int[] array) {
for (int parent= (array.length-1-1)/2; parent >= 0 ; parent--) {
shiftDown(array,parent,array.length);
}
}
//向下调整
private static void shiftDown(int[] array,int parent,int len) {
int child = 2*parent+1;
while(child < len) {
if(child+1 < len && array[child] < array[child+1]){
child++;
}
if (array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}关于排序，下面说法不正确的是
(D)A: 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)B: 归并排序是一种稳定的排序,堆排序和快排均不稳定C: 序列基本有序时，快排退化成冒泡排序，直接插入排序最快D: 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)堆排序空间复杂度的为O(1)
6.冒泡排序
基本思想：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复的进行上面的步骤，直到没有再需要交换的
基本步骤
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-i-1; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
}
}
}
}（2）如果是10个数据 ，假如在第7趟就有序了 ，前面一种还是必须比较9趟，那么能不能优化一下，让值比较7趟就可以了
优化后 时间复杂度O(n)
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-i-1; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flg = true;
}
}
if(flg == false) {
break;
}//这一趟没有发生交换，说明有序
}
}下列排序算法中稳定且时间复杂度为O(n2)的是
(B)A: 快速排序 B: 冒泡排序 C: 直接选择排序 D: 归并排序
7.快速排序（无序使用最好）
基本思想:任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
在写递归的过程中可联想 二叉树的前序遍历 找基准值 进行区间划分
* 时间复杂度：
* 最优：O(n*logn) 每次均分待排序数组
* 最坏：O(n^2) 数组有序或逆序
* 空间复杂度：最好：O(logN)
* 最坏：O(N) 当n足够大时，递归的深度就大
* 稳定性：不稳定7.1 递归实现
7.1.1 Hoare法 找基准
public static void quickSort(int[] array) {
quick(array,0, array.length-1);
}
private static void quick(int[] array,int left, int right) {
//取= 是只有一个节点了 >有可能没有子树
if (left >= right) {
return;
}
int pivot = partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
//找k
private static int partition(int[] array,int start, int end) {
int i = start;
int key = array[start];
while (start < end) {
while (start < end && array[end] >= key) {
end--;
}
while (start < end && array[start] <= key) {
start++;
}
swap(array,start,end);
}
swap(array,start,i);
return start;
}快排在有序情况下，使用可能会栈溢出，所以在使用时要注意这个问题
7.1.2 挖坑法（建议用这个）
注意先走左边
//挖坑法
private static int partition2(int[] array,int start, int end) {
int key = array[start];
while(start < end) {
while(start < end && array[end] >= key) {
end--;
}
array[start] = array[end];
while(start < end && array[start] <= key) {
start++;
}
array[end] = array[start];
}
array[start] = key;
return start;
}7.1.3 前后指针法
private static int partition3(int[] array,int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array[cur] < array[left] && array[++prev] != array[left]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left); return prev;
}🤠 然而，这样写出来的快排，如果实在遇到有序或逆序情况下，可能会栈溢出，所以我们要想办法解决这个问题
那么如何找出三个数字中间大小的数字
上代码
7.1.4 三数取中找基准
private static int midNumIndex(int[] array, int left, int right) {
int mid = (left+right) / 2;
if (array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}else if(array[mid] > array[right]) {
return right;
}else {
return mid;
}
}else {
if(array[mid] > array[left]) {
return left;
}else if(array[mid] < array[right]) {
return right;
}else {
return mid;
}
}
}三数取中递归
private static void quick1(int[] array,int left, int right) {
//取= 是只有一个节点了 >有可能没有子树
if (left >= right) {
return;
}
int index = midNumIndex(array,left,right);
//找到三数中，中间大小的数字，和第一个交换
swap(array,left,index);
//此时就按之前正常那个Hearo法执行就可以了
int pivot = partition1(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}还可以继续改进
既然数组要一层层递归，并且大部分递归的次数，都在最后一层，如果在最后一层时，直接插入排序，那么能否更快一些，并且前面找基准时用上三数取中，更快
private static void quick2(int[] array,int left, int right) {
if(left >= right) {
return;
}
if(right - left + 1 <= 15) {
//趋于有序，用直接插入排序
insertSort2(array,left,right);
return;
}
}
//快排改进后使用的改进插排（给指定的区间进行排序）
private static void insertSort2(int[] array,int start, int end) {
for (int i = start+1; i <= end; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= start; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}7.2 非递归实现
public static void quickSort(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length-1;
//三数取中：解决递归深度问题 基本上 有了三数取中 你的待排序序列 基本上每次都是二分N*logn
int index = midNumIndex(array,left,right);
swap(array,left,index);
int pivot = partition2(array,left,right);
if (pivot > left + 1) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot < right - 1) {
stack.push(pivot + 1);
stack.push(right);
}
while (!stack.empty()) {
right = stack.pop();
left = stack.pop();
pivot = partition1(array, left, right);
//当左边或右边区间只剩一个元素时，不用给栈中放
if (pivot > left + 1) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot < right - 1) {
stack.push(pivot + 1);
stack.push(right);
}
}
}1.快速排序算法是基于()的一个排序算法。
（A）A：分治法 B：贪心法 C：递归法 D：动态规划法2.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是
（A）A: 34，56，25，65，86，99，72，66 B: 25，34，56，65，99，86，72，66C: 34，56，25，65，66，99，86，72 D: 34，56，25，65，99，86，72，66用挖坑法得出选A
8.归并排序
基本思想：归并排序是建立在归并操作上的一种有效的排序算法,
将已有序的子序列合并，得到完全有序的序列；
也就是先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
实现步骤：
* 时间复杂度：O(n*logn)
* 空间复杂度：O(n)
* 稳定性：稳定
* 归并排序8.1 归并排序的递归方法
分割
//分割
private static void mergerSortFunc(int[] array,int left, int right) {
if(left >= right) {
return;
}
// int mid = (left+right)/2;//可能会有整数越界的问题
int mid = left + (right-left)/2;
//1.分解左边
mergerSortFunc(array,left,mid);
//2.分解右边
mergerSortFunc(array,mid+1,right);
//3.进行合并
merge(array,left,right,mid);
}合并
//合并
private static void merge(int[] array,int start, int end, int midIndex) {
//合并放到一个新数组
int[] tmpArr = new int[end-start+1];
int k = 0;//tmpArrA数组下标
int s1 = start;
int s2 = midIndex+1;
//两个归并段，都有数据
while(s1 <= midIndex && s2 <= end) {
if (array[s1] <= array[s2]) {
tmpArr[k++] = array[s1++];
}else {
tmpArr[k++] = array[s2++];
}
}
//此时，说明有个归并段中没有了数据，拷贝到另一半的全部到tmpArr数组中
while(s1 <= midIndex) {
tmpArr[k++] = array[s1++];
}
while(s2 <= end) {
tmpArr[k++] = array[s2++];
}
//把排好序的数组 拷贝回 原来的数组
for (int i = 0; i < k; i++) {
array[i+start] = tmpArr[i];
}
} public static void mergerSort(int[] array) {
mergerSortFunc(array,0, array.length-1);
}8.2 归并排序的非递归方法
public static void mergerSort2(int[] array) {
int gap = 1;//每组的数据
while(gap < array.length) {
for (int i = 0; i < array.length; i += gap*2) {
int s1 = i;
int e1 = s1+gap-1;
if(e1 >= array.length) {
e1 = array.length-1;
}
int s2 = e1+1;
if(s2 >= array.length) {
s2 = array.length -1;
}
int e2 = s2+gap-1;
if (e2 >= array.length) {
e2 = array.length-1;
}
merge(array,s1,e2,e1);
}
gap *= 2;
}
}以下排序方式中占用O(n)辅助存储空间的是
(D)A: 简单排序 B: 快速排序 C: 堆排序 D: 归并排序
9.计数排序（不比较）
基本思想：计数排序通过计算数组中每个元素的出现次数来对数组的元素进行排序。将计数存储在辅助数组中，并通过将计数映射为辅助数组的索引来完成排序。
实现步骤
public static void countSort(int[] array) {
int maxVal = array[0];
int minVal = array[0];
for (int i = 0; i < array.length; i++) {
if(array[i] < minVal) {
minVal = array[i];
}
if (array[i] > maxVal) {
maxVal = array[i];
}
}
//确定了最大 最小值
int len = maxVal - minVal + 1;
int[] count = new int[len];
//开始遍历array数组 进行计数
for (int i = 0; i < array.length; i++) {
int val = array[i];
count[val-minVal]++;
}
int index = 0;//array数组下标
for (int i = 0; i < count.length; i++) {
//确保当前count数组 可以检查完
while(count[i] != 0) {
array[index] = i + minVal;
index++;
count[i]--;
}
}
}10. 基数排序
基本思想：基数排序是利用分配和收集两种基本操作。
基数排序是一种按记录关键字的各位值逐步进行排序的方法。
此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。
实现步骤：
private static void radixSort(int[] arr) {
//待排序列最大值
int max = arr[0];
int exp;//指数
//计算最大值
for (int anArr : arr) {
if (anArr > max) {
max = anArr;
}
}
//从个位开始，对数组进行排序
for (exp = 1; max / exp > 0; exp *= 10) {
//存储待排元素的临时数组
int[] temp = new int[arr.length];
//分桶个数
int[] buckets = new int[10];
//将数据出现的次数存储在buckets中
for (int value : arr) {
//(value / exp) % 10 :value的最底位(个位)
buckets[(value / exp) % 10]++;
}
//更改buckets[i]，
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
}
//将数据存储到临时数组temp中
for (int i = arr.length - 1; i >= 0; i--) {
temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
}
//将有序元素temp赋给arr
System.arraycopy(temp, 0, arr, 0, arr.length);
}
}11. 桶排序
基本思想：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了
实现步骤：
public static void bucketSort(int[] arr){
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 计算桶的数量
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
arr[index++] = bucketArr.get(i).get(j);
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/91246.html
