我要评论一.前言:
在大一下学期学习C语言的时候已经了解过了冒牌排序和选择排序.下个学期有数据结构这门课,所以最近有在先了解数据结构,学习了两种新的排序方法,使用了Java语言进行实现
二.插入排序
插入排序的思想其实很好理解，比如说学生按照身高排位置。最经典的解释就是:在生活,假如我们需要对N个同学进行身高排序,假定前N-1个同学是有序的，那么第N个同学就一个一个从低到高比较，找到合适的位置插入即可。
1 动画展示
备注：
黄色部分：已经排好序的元素
青色部分：将要排序的元素
底部红色：正在排序的元素
2 代码实现
- display函数(用以展示数组元素)
//display函数(用以展示数组元素)
public static void display(int arr[]){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
- 插入排序函数
//普通插入排序方法
public static void insertOne(int arr[]){
int counter = 1;//记录第几轮的轮数
for (int i = 1; i <arr.length ; i++) {//默认第一个数已经排好序,故i=1
// temp:表示待排序的元素，也就是以上动图中青色部分的元素。
int temp = arr[i];
//insertPoint:插入点,即已排好序部分的最后一个数索引值
int insertPoint = i - 1;
//插入排序逻辑
while(insertPoint>=0&&arr[insertPoint]>temp){
//当前已排好元素比待排序元素temp大,当前元素后移,留出地方给temp插入
//后移
arr[insertPoint+1] = arr[insertPoint];
//插入点前移
insertPoint--;
}
//不符合条件的时候,停止循环,插入元素
arr[insertPoint + 1] = temp;
display(arr);
System.out.println("");
}
}
- 完整代码
package com.homyit;
public class InsertSortDemo {
//display函数(用以展示数组元素)
public static void display(int arr[]){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
//插入排序方法
public static void insertOne(int arr[]){
int counter = 1;//记录第几轮的轮数
for (int i = 1; i <arr.length ; i++) {//默认第一个数已经排好序,故i=1
// temp:表示待排序的元素，也就是以上动图中青色部分的元素。
int temp = arr[i];
//insertPoint:插入点,即已排好序部分的最后一个数索引值
int insertPoint = i - 1;
//插入排序逻辑
while(insertPoint>=0&&arr[insertPoint]>temp){
//当前已排好元素比待排序元素temp大,当前元素后移,留出地方给temp插入
//后移
arr[insertPoint+1] = arr[insertPoint];
//插入点前移
insertPoint--;
}
//不符合条件的时候,停止循环,插入元素
arr[insertPoint + 1] = temp;
display(arr);
System.out.println("");
}
}
public static void main(String[] args) {
int a [] = {56,32,11,55,31,15};
insertOne(a);
}
}
输出结果:
32 56 11 55 31 15
11 32 56 55 31 15
11 32 55 56 31 15
11 31 32 55 56 15
11 15 31 32 55 56
三.快速排序
快速排序它的特点就像名字一样速度快、效率高。快速排序采用的思想是分治思想，先简单的介绍一下分治,即分而治之的思想。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题
一组待排数据，选择一个基准元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,然后对这两部分重复同样的操作。
快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot）。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
1 动画展示
2 代码实现
- display函数(用以展示数组元素)
//display函数(用以展示数组元素)
public static void display(int arr[]){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
- 快速排序代码
public static void quickSort(int arr[],int low,int high){
//递归结束条件
if(low >= high){
return;
}
//保存低位和高位
int left = low;//左指针
int right = high;//右指针
int pivot = arr[low];//选取第low个元素作为基准值
//通过第一个循环将小的数字分配到基准数左边,
//大的放在右边,标准数放在中间
//循环结束的条件即为两个指针相遇(low==high)
while(left<right){
//从右往左寻找比基准大的元素
while(left < right&&arr[right] >= pivot){
//右指针-1继续比较
right--;
}
//找到比基准数小的元素放在左指针出,此时的left即low
arr[left] = arr[right];
//再从左往右寻找比基准小的元素
while(left < right&&arr[left] <= pivot){
//左指针+1继续比较
left++;
}
//找到比基准大的元素放在right索引出
arr[right] = arr[left];
}
//再次设置基准值
arr[left] = pivot;
System.out.println("low:"+low+"--high:"+high+"--"+ Arrays.toString(arr));
quickSort(arr,low,left - 1);//将左边数组再次快排
quickSort(arr,left + 1,high);//右边快排
}
- 全部代码
package com.homyit;
import java.util.Arrays;
public class QuickSortDemo {
//display函数(用以展示数组元素)
public static void display(int arr[]){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public static void quickSort(int arr[],int low,int high){
//递归结束条件
if(low >= high){
return;
}
//保存低位和高位
int left = low;//左指针
int right = high;//右指针
int pivot = arr[low];//选取第low个元素作为基准值
//通过第一个循环将小的数字分配到基准数左边,
//大的放在右边,标准数放在中间
//循环结束的条件即为两个指针相遇(low==high)
while(left<right){
//从右往左寻找比基准大的元素
while(left < right&&arr[right] >= pivot){
//右指针-1继续比较
right--;
}
//找到比基准数小的元素放在左指针出,此时的left即low
arr[left] = arr[right];
//再从左往右寻找比基准小的元素
while(left < right&&arr[left] <= pivot){
//左指针+1继续比较
left++;
}
//找到比基准大的元素放在right索引出
arr[right] = arr[left];
}
//再次设置基准值
arr[left] = pivot;
System.out.println("low:"+low+"--high:"+high+"--"+ Arrays.toString(arr));
quickSort(arr,low,left - 1);//将左边数组再次快排
quickSort(arr,left + 1,high);//右边快排
}
public static void main(String[] args) {
int a [] = {56,32,11,55,31,15};
display(a);
quickSort(a,0,5);
System.out.println("");
display(a);
}
}
输出结果:
56 32 11 55 31 15
low:0–high:5–[15, 32, 11, 55, 31, 56]
low:0–high:4–[11, 15, 32, 55, 31, 56]
low:2–high:4–[11, 15, 31, 32, 55, 56]11 15 31 32 55 56
四.两种排序的比较
| 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n^2) | O(nlog2n) | O(nlog2n) | 不稳定 |
本文地址：https://blog.csdn.net/storm_55/article/details/107701776
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论