- 稳定性
- 1.插入排序
- 1.1思路:
- 1.2代码
- 1.3复杂度
- 1.4.特点:
- 2.希尔排序
- 2.1思路
- 2.2代码
- 2.3复杂度
- 2.4特点
- 3.选择排序
- 3.1思路
- 3.2代码
- 3.3复杂度
- 4.堆排序
- 4.1思路
- 4.2代码
- 4.3复杂度
- 5.冒泡排序
- 5.1思路
- 5.2代码
- 5.3复杂度
- 6.快速排序
- 6.1思路
- 6.2代码
- 6.3复杂度
- 7.归并排序
- 7.1思路
- 7.2代码
- 7.3复杂度
稳定性
两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算法是具备稳定性的排序算法。
1.插入排序 1.1思路:
1.将整个队列分为已排序区间和待排序区间
2.每次选择待排序区间的第一个元素,和已排序区间的最后一个元素比较,按照所需要的顺序选择合适的位置插入。
这样依次类推。
1.2代码注意:并不是将两个数交换,而是将较大的数后移。例如上图,待排序第一个为5,将5和9比较,小于9,则将9往后移一位,在和6比较,小于6,将6的位置也往后移一位,再将5和4比较,大于,于是就将5插入到4和6中间的位置。
//插入排序
public static void insertSort(int[] arr){
int bound = 1;
//[0,bound)是已排序区间
//[bound,length)待排序区间
for(;bound < arr.length;bound++){
int num = arr[bound];
int i = bound - 1;
for(;i >= 0;i--){
if(num < arr[i]){
//说明num应该插入到arr[i]之前,于是就把i的位置往后搬运一位
arr[i + 1] = arr[i];
}else {
//说明已经找到合适的位置 了,可以结束循环了
break;
}
}
arr[i + 1] = num;
}
}
1.3复杂度
时间复杂度:O(N ^ 2);
空间复杂度:O(1);
(1)如果数组长度比较短,排序效率很高
(2)如果数组相对有序,那么排序效率也很高
(稳定排序)
2.希尔排序
(针对插入排序进一步改进)
2.1思路
(图源自浏览器)
- 针对序列进行分组,针对每一个分组分别进行插入排序
- 随之调整分组的变化,逐渐使整个数组逼近有序的状态
(常见的序列选择:size/2,size/4,size/8……直到1(也叫希尔序列))
可以看到,此时相比之前已经相对有序多了,在gap = 1,也就是插入排序最终可得有序的状态:
//希尔排序
public static void shellSort(int[] arr){
//指定gap序列:
int gap = arr.length/2;
while (gap >= 1){
//构造辅助函数来帮助排序
_shellSort(arr,gap);
gap = gap/2;
}
}
private static void _shellSort(int[] arr,int gap) {
//进行分组插排,分成gap组,同组的相邻元素的下标差值为gap
//和插入排序是一样的(如果gap = 1,就完全一样)
int bound = gap;
for(;bound < arr.length;bound++){
int num = arr[bound];
int cur = bound - gap;//同组的相邻元素的下标差值为gap,所以减gap
//同插入排序
for(;cur >= 0; cur-=gap){
if(arr[bound] < arr[cur]){
arr[cur + gap] =arr[cur];
}else{
break;
}
}
arr[cur + gap] = num;
}
}
2.3复杂度
时间复杂度:O(N ^ 2);
空间复杂度:O(1);
(不稳定排序)
希尔排序就是利用了插入排序的两个特点,将长队列划分成短的队列,分别使他们有序来提升效率
(实际上用处不太大)
3.选择排序 3.1思路
遍历待排序区间,将第一个元素和后面的所有元素进行对比,顺序不对则交换这两个元素。第一轮遍历完成后,再从第二个元素开始和后面的进行对比。以此类推。
此时,第一轮遍历结束,第一个元素已排好序,接下来排第二个元素
依次类推,最终排序成功
3.2代码//选择排序
public static void selectSort(int[] arr){
for(int i = 0;i < arr.length - 1;i++){
for(int j = i + 1;j < arr.length;j++){//首先和该元素后面的那个数对比,所以是i+1
//如果顺序不对就交换
if(arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
3.3复杂度
时间复杂度:O(N ^ 2);
空间复杂度:O(1)
(不稳定排序)
4.堆排序
(本质上是优化的选择排序)
4.1思路(待补充)
4.2代码 //堆排序
public static void heapSort(int[] arr){
//1.先建立堆
creatHeap(arr);
//2.需要循环取出堆顶元素,和最后一个元素交换并删除,再从0位置进行调整
int heapSize = arr.length;//堆的大小
for(int i = 0;i < arr.length; i++){
//交换0号元素和堆的最后一个元素
swap(arr,0,heapSize - 1);
//把最后一个元素从堆上删除
heapSize--;
//从0号位置开始往下进行调整
shiftDown(arr,heapSize,0);
}
}
private static void creatHeap(int[] arr) {
for (int i = (arr.length - 1 - 1) / 2; i >= 0 ; i--) {
shiftDown(arr,arr.length,i);
}
}
private static void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
private static void shiftDown(int[] arr, int size, int index) {
int parent = index;
int child = 2 *parent + 1;
while (child < size){
//先找出左右子树比较大的
if(child + 1 < size && arr[child + 1] > arr[child]){
child = child + 1;
}
//在比较child和parent
if(arr[child] > arr[parent]){
swap(arr,parent,child);
}else{
break;
}
parent = child;
child = 2 *parent + 1;
}
}
4.3复杂度
时间复杂度:O(n * log(n))
空间复杂度:O(1)
(不稳定排序)
5.冒泡排序 5.1思路
(以升序为例)比较两个相邻元素,不符合顺序要求就交换,这样一趟下来就能让最小的元素走到数组的最前(从后往前排)(从前往后排:让最大的元素走到数组的最后)并且就将数组分为已排序区间和待排序区间
//冒泡排序(这个代码是从后往前排,从前往后排原理一样)
public static void bubbleSort(int[] arr){
//bound用来区分两个区间
//第一趟结束后,第一个元素就是最小的元素 ,就位于已排序区间,下面的排序就排序到已排序区间的后面
for(int bound = 0;bound < arr.length;bound++){
for(int cur = arr.length - 1; cur > bound ; cur --){
if(arr[cur - 1] > arr[cur]){
int tmp = arr[cur - 1];
arr[cur - 1] = arr[cur];
arr[cur] = tmp;
}
}
}
5.3复杂度
时间复杂度:O(N ^ 2);
空间复杂度:O(1);
稳定排序
6.快速排序 6.1思路
- 从待排序区间选择一个数,作为基准值(pivot);
- Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基
准值大的(可以包含相等的)放到基准值的右边; - 采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度 == 1,代表已经有序,
或者小区间的长度 == 0,代表没有数据
//快速排序
public static void quickSort(int[] arr){
//创建辅助递归的方法,这个方法的参数中,明确指定针对哪个区间进行递归[0,length - 1]
_quickSort(arr,0,arr.length - 1);
}
public static void _quickSort(int[] arr, int left, int right) {
if(left >= right){
//如果当前的区间为空,或者只有一个元素,都不需要进行任何处理
return;
}
//针对[left,right]区间进行partition操作,方法的返回值,表示整理完当前区间后,基准值所在的位置
//遍历过程中的left和right重合的位置
int index = partition(arr,left,right);
//递归的对左侧区间进行快速排序
_quickSort(arr,left,index- 1);
//递归的对右侧区间进行快速排序
_quickSort(arr,index+1,right);
}
public static int partition(int[] arr, int left, int right) {
//选取最右侧元素作为基准值,
int v = arr[right];
int l = left;
int r = right;
//如果l和r重合,说明遍历完成
while (l < r){
//先从左往右,找一个比基准值大的数字
while (l < r && arr[l] <= v){
l++;
}
//再从右往左找一个比基准值小的数字
while (l < r && arr[r] >= v){
r--;
}
//找到后 将他两交换
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
//当l和r重合的时候,就把重合位置的元素和基准值位置进行交换
int tmp = arr[l];
arr[l] = arr[right];
arr[right] = tmp;
//返回基准值位置
return l;
}
6.3复杂度
时间复杂度:O(NlogN)(平均)
空间复杂度:O(logN)(平均)
不稳定排序
7.归并排序 7.1思路
(代补充)
7.2代码//归并排序
public static void mergeSort(int[] arr){
_mergeSort(arr,0,arr.length);
}
public static void _mergeSort(int[] arr, int left, int right) {
if(right - left <= 1){
//判定当前区间是不是只右一个元素或者没有元素,此时不需要排序
return;
}
int mid = (left + right)/2;
//先让[left,right)区间变成有序
_mergeSort(arr,left,mid);
//再让[mid,right区间变成有序)
_mergeSort(arr, mid, right);
//合并两个有序区间
merge(arr,left,mid,right);
}
//归并排序中的关键操作,就是归并两个有序数组
//使用该merge方法来完成数组归并的过程
// 此处两个数组就通过参数的left,mid,right描述
//[left,mid)左侧数组,[mid,right)右侧数组
public static void merge(int[] arr,int left,int mid,int right){
//具体的归并操作,需要创建一个临时的空间来保存归并的结果
//临时的空间得能保存的下带归并的两个数组 也就是right - left这么长
int[] tmp = new int[right - left];
int tmpIndex = 0;//表示当前元素该放到临时空间的哪个位置上
int cur1 = left;
int cur2 = mid;
while (cur1 < mid && cur2 < right){
if(arr[cur1] <= arr[cur2]){
//把cur1对应的元素插入到临时空间中
tmp[tmpIndex] = arr[cur1];
tmpIndex++;
cur1++;
}else {
//把cur2对应的元素插入到临时空间中
tmp[tmpIndex] = arr[cur2];
tmpIndex++;
cur2++;
}
}
//循环结束后,需要把剩余的元素也都拷贝到最终结果里
while(cur1 < mid){
tmp[tmpIndex] = arr[cur1];
tmpIndex++;
cur1++;
}
while(cur2 < mid){
tmp[tmpIndex] = arr[cur2];
tmpIndex++;
cur2++;
}
//把tmp的结果再放回arr数组(原地排序){
for(int i = 0;i < tmp.length;i++){
arr[left + i] = tmp[i];
}
}
7.3复杂度
时间复杂度:O(N * log(N));
空间复杂度:O(N);
稳定排序


![[排序]稳定性、插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序 [排序]稳定性、插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序](http://www.mshxw.com/aiimages/31/937702.png)
