作者简介：大家好，我是IT界的小学生——郭嘉烨常用的几个排序算法
博客主页：郭嘉烨的CSDN博客主页
您的点赞评论，支持是我创作的最大动力！！！
1.冒泡排序
2.选择排序
3.插入排序
4.希尔排序
5.归并排序
【Java|【数据结构与算法】——必知必会的排序算法你会几种】6.快速排序
1.冒泡排序 算法原理：
- 从第一个元素开始，比较相邻的两个元素，如果第一个大于第二个，则交换它们
- 对每一对相邻的元素做相同的操作，从第一对到最后一对，最终最后一位元素就是最大值
- 对每一个元素重复上述步骤，最后一个除外
文章图片
java实现代码：
public class Bubble {
//数组排序
public static void sort(Comparable[] a){
for (int i = a.length - 1;
i > 0;
i--){
for (int j = 0;
j < i;
j++){
if (greater(a[j],a[j + 1])){
swap(a,j,j + 1);
}
}
}
}
//比较 v 是否大于 w
public static boolean greater(Comparable v,Comparable w){
return v.compareTo(w) > 0;
}
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}public class BubbleTest {
public static void main(String[] args) {
Integer[] arr = {3,5,9,7,2,1};
Bubble.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前：{3,5,9,7,2,1}
//排序后：{1,2,3,5,7,9}2.选择排序 算法原理：
- 每次从待排序的数据元素中选择最小值或最大值，放在第一位
- 从剩余的元素中继续寻找最小或最大元素，放在已排序元素的后面
- 重复以上步骤，直到排序完成
文章图片
java代码实现：
public class SelectionSort {
//选择排序
public static void sort(Comparable[] a){
for (int i = 0;
i <= a.length - 2;
i++){
//定义一个变量，记录最小元素的索引
int minIndex = i;
for (int j = i + 1;
j < a.length;
j++){
//比minIndex与j两个索引处的值的大小
if (greater(a[minIndex],a[j])){
minIndex = j;
}
}
//交换最小元素的所在索引minIndex处的值与索引值为i的元素的值
swap(a,i,minIndex);
}
}
//比较 v 是否大于 w
public static boolean greater(Comparable v,Comparable w){
return v.compareTo(w) > 0;
}
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}public class SelectionSortTest {
public static void main(String[] args) {
Integer[] arr = {9,18,38,2,46,8,43,46,5,12};
SelectionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前：{9,18,38,2,46,8,43,46,5,12}
//排序后：{2,5,8,9,12,18,38,43,46,46}3.插入排序 算法原理：
- 把所有元素分为两个序列，将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从未排序序列中的第一个元素开始，向已排序的序列中插入
- 倒序遍历已排序序列，依次和待插入的元素比较，找到一个小于或等于待插入的元素，插入到该元素后面，其余元素向后移动一位
文章图片
java代码实现
public class InsertionSort {
//插入排序
public static void sort(Comparable[] a){
for (int i = 1;
i < a.length;
i++){
for (int j = i;
j > 0;
j--){
//比较索引j处的值与索引j-1处的值,如果j-1索引处的值大，则交换数据，反之，则找到了合适的位置，退出循环
if (greater(a[j - 1],a[j])){
swap(a,j - 1,j);
}else{
break;
}
}
}
}
//比较 v 是否大于 w
public static boolean greater(Comparable v,Comparable w){
return v.compareTo(w) > 0;
}
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}public class InsertionSortTest {
public static void main(String[] args) {
Integer[] arr = {3,44,38,5,47,15,36,26,27};
InsertionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前：{3,44,38,5,47,15,36,26,27}
//排序后：{3,5,15,26,27,36,38,44,47}4.希尔排序 算法原理：
- 选择一个增长量h，按照增长量h作为数据分组的依据对数据分组
- 对分好的每一组完成插入排序
- 减小增长量，最小减为一，重复第二步
文章图片
java代码实现：
public class ShellSort {
//希尔排序
public static void sort(Comparable[] a){
?
int h = 1;
while (h < a.length / 2){
h = 2 * h + 1;
}
while (h >= 1){
//找到待插入的元素
for (int i = h;
i = h;
j-=h) {
if (greater(a[j - h],a[j])){
swap(a,j - h,j);
}else{
break;
}
}
}
//减小h的值
h = h / 2;
}
?
}
//比较 v 是否大于 w
public static boolean greater(Comparable v,Comparable w){
return v.compareTo(w) > 0;
}
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}public class ShellSortTest {
public static void main(String[] args) {
Integer[] arr = {86,11,54,34,53,12,45,81,19,65};
ShellSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前：{86,11,54,34,53,12,45,81,19,65}
//排序后：{11,12,19,34,45,53,54,65,81,86}5.归并排序 算法原理：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤c直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
文章图片
java代码实现：
public class MergeSort {
//归并所需的辅助数组
private static Comparable[] assist;
?
//比较 v 是否小于 w
public static boolean less(Comparable v,Comparable w){
return v.compareTo(w) < 0;
}
?
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//排序
public static void sort(Comparable[] a){
//初始化辅助数组
assist = new Comparable[a.length];
int l = 0;
int h = a.length - 1;
sort(a,l,h);
}
?
private static void sort(Comparable[] a,int l,int h){
if (h <= l){
return;
}
//分组
int mid = l +(h - l) / 2;
//分别对每组数据排序
sort(a,l,mid);
sort(a,mid + 1,h);
//对数组进行归并
merge(a,l,mid,h);
}
?
//对数组进行归并
private static void merge(Comparable[] a,int l,int mid,int h){
//定义三个指针
int i = l;
int p1 = l;
int p2 = mid + 1;
//遍历，移动p1,p2指针，比较两处索引的值,小的放到辅助数组的对应索引处
while (p1 <= mid && p2 <=h){
if (less(a[p1],a[p2])){
assist[i++] = a[p1++];
}else {
assist[i++] = a[p2++];
}
}
//遍历数组，如果p1的指针没有走完，则顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
while (p1 <= mid){
assist[i++] = a[p1++];
}
//遍历数组，如果p2的指针没有走完，则顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
while (p2 <= h){
assist[i++] = a[p2++];
}
//把辅助数组中的元素拷贝到原数组中
for (int j = l;
j <= h;
j++) {
a[j] = assist[j];
}
}
}public class MergeSortTest {
public static void main(String[] args) {
Integer[] arr = {5,6,3,1,8,7,2,4};
MergeSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前：{5,6,3,1,8,7,2,4}
//排序后：{1,2,3,4,5,6,7,8}6.快速排序 算法原理：
- 从数列中挑出一个元素作为基准点
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
- 然后基准值左右两边，重复上述步骤
- 通过递归把基准值元素左右两侧的数组排序，排完之后，整个数组就排序完成了
文章图片
java代码实现：
public class QuickSort {
//比较 v 是否小于 w
public static boolean less(Comparable v,Comparable w){
return v.compareTo(w) < 0;
}
?
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//排序
public static void sort(Comparable[] a){
int l = 0;
int h = a.length - 1;
sort(a,l,h);
}
?
private static void sort(Comparable[] a,int l,int h){
if (h <= l)return;
//对数组进行分组(左右两个数组)
// i 表示分组之后基准值的索引
int i = partition(a, l, h);
//让左边的数组有序
sort(a,l,i - 1);
//让有边的数组有序
sort(a,i + 1,h);
}
?
public static int partition(Comparable[] a,int l,int h){
//确定基准值
Comparable key = a[l];
//定义两个指针
int left = l;
int right = h + 1;
//切分
while (true){
//从右向左扫描，移动right指针找一个比基准值小的元素，找到就停止
while (less(key,a[--right])){
if (right == l)
break;
}
//从左向右扫描，移动left指针找一个比基准值大的元素，找到就停止
while (less(a[++left],key)){
if (left == h)
break;
}
if (left>=right){
break;
}else {
swap(a,left,right);
}
}
//交换基准值
swap(a,l,right);
return right;
}
}public class QuickSortTest {
public static void main(String[] args) {
Integer[] arr = {3,1,2,4,9,6};
QuickSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前：{3,1,2,4,9,6}
//排序后：{1,2,3,4,6,9}推荐阅读
- 数据结构与算法|数据结构与算法 | 用Java语言实现顺序表真的不难
- Java|Java基础——面向基础模块
- Java|阿里云——Java实现手机短信验证码功能
- Java|Java实现短信验证码
- 进阶之路|大聪明教你学Java | 面试官（请你说说 Redis 为什么这么快（））
- 程序人生|关于程序员35岁的坎（年龄不是挡板，当你匹配了这个年纪该有的能力还有什么畏惧！）
- Java全家桶
- R编程中的数据结构介绍
- java|动态规划刷题攻略(二)