- 1. Comparable接口
- 2.冒泡排序（Bubble Sort）
- 2.1 排序原理：
- 2.2 时间复杂度分析
- 2.3 程序代码
- 3.选择排序（Selection sort）
- 3.1 排序原理
- 3.2 时间复杂度分析
- 3.3 程序代码
- 4 .插入排序（Insertion sort）
- 4.1 排序原理（扑克牌）
- 4.2 时间复杂度
- 4.3 程序代码：
- 高级排序
- 5. 希尔排序（shell sort）（插入排序）
- 5.1 排序原理
- 5.2 程序代码
- 6. 归并排序(Merge sort)
- 6.1 递归
- 6.2 递归实现N的阶乘-N!
- 归并排序
- 6.3 排序原理
- 6.4 时间复杂度
- 6.5 代码实现
- 7. 快速排序（Quick sort）
- 7.1 排序原理
- 7.2 切分原理
- 7.4 实现代码
- 8. 各种排序算法效率比较（重点）
- 冒泡排序、选择排序、插入排序的直接实现代码
- 源码地址
- 学习视频网站：（哔哩哔哩）
题目：
定义一个学生类，通过Comparable接口提供比较规则
package study.demo;
/**
定义一个学生类，通过Comparable接口提供比较规则
*/
public class ComparableStudent implements Comparable<ComparableStudent>{
private Integer age;
private String student;
public ComparableStudent(Integer age, String student) {
this.age = age;
this.student = student;
}
public ComparableStudent() {
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
public String getStudent() {
return student;
}
public void setStudent(String student) {
this.student = student;
}
@Override
public String toString() {
return "ComparableStudent{" +
"age=" + age +
", student='" + student + '\'' +
'}';
}
/**
* 定义比较规则
* @param o
* @return
*/
public int compareTo(ComparableStudent o) {
System.out.println(this.age);//18
System.out.println(o.age);//15
System.out.println(this.age-o.age);//3
return this.age-o.age;
}
/**
* 定义比较方法：
* ① 如果result>0 c1>c2
* ② 如果result<0 c1
static Comparable getMax(Comparable c1,Comparable c2 ){
int result=c1.compareTo(c2);//谁在前，谁为本类对象
if(result>=0){
return c1;
}else {
return c2;
}
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
ComparableStudent c1 = new ComparableStudent(18, "小红");
ComparableStudent c2 = new ComparableStudent(15, "小名");
//输出最大的值
//比较方法：comparable
Comparable max=getMax(c1,c2);
System.out.println(max);
/*
结果：
ComparableStudent{age=18, student='小红'}
*/
}
}
a.比较相邻的元素，如果前一个元素比后一个元素大，就交换这两个元素的位置。
b.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对元素。最终最后位置的元素就是最大值。
总执行次数：N^2-N
时间复杂度：O(N^2)
package study.demo;
import java.util.Arrays;
/**
* 冒泡排序
*/
public class Bubble {
/**
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
//{6,5,4,3,2,1}
//比较索引j和索引j+1处的值
if (greater(a[j],a[j+1])){
exch(a,j,j+1);
}
}
}
}
/**
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/**
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
/**
* 测试程序
* @param args
*/
public static void main(String[] args) {
Integer[] arr = {4,5,6,3,2,1};
Bubble.sort(arr);
System.out.println(Arrays.toString(arr));//{1,2,3,4,5,6}
}
}
a.每次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引出的值为最小值，最后可以找到最小值所在的索引。
b.交换第一个索引处和最小值所在的索引处的值。
总执行次数：N^2/2+N/2-1
时间复杂度：O(N^2)
package study.sort;
import java.util.Arrays;
/**
* 选择排序
*/
public class Selection {
/**
对数组a中的元素进行排序
*/
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处的值
exch(a,i,minIndex);
}
}
/**
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/**
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
/**
* 测试
*/
public static void main(String[] args) {
//原始数据
Integer[] a = {4,6,8,7,9,2,10,1};
Selection.sort(a);
System.out.println(Arrays.toString(a));
//{1,2,4,5,7,8,9,10}
}
}
a.把所有的元素分为两组，已经排序和未排序的。
b.找到未排序的组中的第一个元素，向已经排序的组中进行插入。
c.倒序遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他元素向后移动一位。
总执行次数：N^2-N
时间复杂度：O(N^2)
package study.sort;
import java.util.Arrays;
/**
* 插入排序
*/
public class Insertion {
/**
对数组a中的元素进行排序
*/
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处的值比索引j处的值大，则交换数据，如果不大，那么就找到合适的位置了，退出循环即可；
if (greater(a[j-1],a[j])){
exch(a,j-1,j);
}else{
break;
}
}
}
}
/**
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/**
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
/**
* 测试
*/
public static void main(String[] args) {
Integer[] a = {4,3,2,10,12,1,5,6};
Insertion.sort(a);
System.out.println(Arrays.toString(a));
//{1,2,3,4,5,6,10,12}
}
}
以上三种时间复杂度均为平方阶，随着输入规模的增大，时间成本将急剧上升，不能处理更大规模的问题。
高级排序 5. 希尔排序（shell sort）（插入排序）希尔排序是插入排序的一种，又称"缩小增量排序"，是插入排序的更高效的改进版本。
5.1 排序原理a.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
b.对分好组的每一组数据完成插入排序；
c.减少增长量，最少减为1，重复第二步 *** 作。
package study.sort;
import java.util.Arrays;
/**
* 希尔排序
*/
public class Shell {
/**
* 对数据a中的元素进行排序
*/
public static void sort(Comparable[] a){
//1.根据数组a的长度，确定增长量h的初始值
int h=1;
while(h<a.length/2){
h=2*h+1;
}
//减少的规则 h=h/2
while(h>=1){
//排序
//找到待插入的元素
for(int i=h;i<a.length;i++){
//把待插入的元素插入到有序数组中
for(int j=i;j>=h;j-=h){
if(greater(a[j-h],a[j])){
exch(a,j-h,j);//为int类型，而a为Comparable类型
}else {
//待插入元素已经找到了合适的位置，结束循环；
break;//break语句对if-else的条件语句不起作用,跳出的是for循环
}
}
}
h=h/2;
}
}
/**
* 比较v元素是否大于w的元素
*
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/**
* 交换元素
*
*/
private static void exch(Comparable[] a,int i,int j){
//定义临时变量
Comparable temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
/**
* 测试希尔排序
*/
public static void main(String[] args) {
Integer arr[] ={1,5,7,1,8,56,1,78,16,95,188,188,11,566};
//放进接口排序,Comparable只针对对象排序
sort(arr);
//打印输出数组
System.out.println(Arrays.toString(arr));
}
}
定义：定义方法时，在方法内部调用方法本身，称之为递归。
作用：它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来求解。递归策略只需要少量程序即可描述出解题过程所需要的多次重复计算，大大的减少了程序的代码量。但是，必须有边界条件，否则递归的层级太深，容易造成栈内存溢出。
public static void show(){
System.out.println("递归");
show();
}
public static Integer factorial(int n){
if(n==1){
return 1;
}
return n*factorial(n-1);
}
(超过23就会溢出)
归并排序 6.3 排序原理定义：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若两个有序表合并成一个有序表，称为二路归并。
原理：
a.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
b.将相邻的两个子组进行合并成一个有序的大组。
c.不断地重复步骤b,直到最终只有一个组为止。
package study.sort;
import java.util.Arrays;
/**
* 归并排序
*/
public class MergeSort {
/**
* 1. 递归（recursion）：调用方法本身
*/
public static void show(){
System.out.println("递归");
show();
}
/**
* 递归算法实现N的阶乘 N!
*/
public static Integer factorial(int n){
if(n==1){
return 1;
}
return n*factorial(n-1);
}
/**
归并所需要的辅助数组
*/
private static Comparable[] assist;
/**
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w)<0;
}
/**
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
//1.初始化辅助数组assist；
assist = new Comparable[a.length];
//2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引；
int lo=0;
int hi=a.length-1;
//3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
sort(a,lo,hi);
}
/**
对数组a中从lo到hi的元素进行排序
*/
private static void sort(Comparable[] a, int lo, int hi) {
//做安全性校验；
if (hi<=lo){
return;
}
//对lo到hi之间的数据进行分为两个组
int mid = lo+(hi-lo)/2;// 5,9 mid=7
//分别对每一组数据进行排序
sort(a,lo,mid);
sort(a,mid+1,hi);
//再把两个组中的数据进行归并
merge(a,lo,mid,hi);
}
//1、重载是指不同的函数使用相同的函数名，但是函数的参数个数或类型不同。调用的时候根据函数的参数来区别不同的函数。
//
//2、覆盖（也叫重写）是指在派生类中重新对基类中的虚函数（注意是虚函数）重新实现。即函数名和参数都一样，只是函数的实现体不一样。
/**
（重载） 对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
//定义三个指针
int i=lo;
int p1=lo;
int p2=mid+1;
//遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
while(p1<=mid && p2<=hi){
//比较对应索引处的值
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<=hi){
assist[i++]=a[p2++];
}
//把辅助数组中的元素拷贝到原数组中
for(int index=lo;index<=hi;index++){
a[index]=assist[index];
}
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
Integer a[]={1,55,155,1185,11,89,11,99,1,99,1,96,6,19,78};
MergeSort.sort(a);
System.out.println(Arrays.toString(a));
//实现N的阶乘-超过23就会溢出
System.out.println(factorial(23));
}
}
1.首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于
或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两
部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当
左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
切分原理：
把一个数组切分成两个子数组的基本思想：
1.找一个基准值，用两个指针分别指向数组的头部和尾部；
2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.交换当前左边指针位置和右边指针位置的元素；
5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
package study.sort;
import java.util.Arrays;
/**
* 快速排序
*/
public class Quick {
/**
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/**
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
//对数组内的元素进行排序
public static void sort(Comparable[] a) {
int lo = 0;
int hi = a.length-1;
sort(a,lo,hi);
}
//对数组a中从索引lo到索引hi之间的元素进行排序
private static void sort(Comparable[] a, int lo, int hi) {
//安全性校验
if (hi<=lo){
return;
}
//需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；
int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引
//让左子组有序
sort(a,lo,partition-1);
//让右子组有序
sort(a,partition+1,hi);
}
//对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引
public static int partition(Comparable[] a, int lo, int hi) {
//确定分界值
Comparable key = a[lo];
//定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
int left=lo;
int right=hi+1;
//切分
while(true){
//先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
while(less(key,a[--right])){
if (right==lo){
break;
}
}
//再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
while(less(a[++left],key)){
if (left==hi){
break;
}
}
//判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
if (left>=right){
break;
}else{
exch(a,left,right);
}
}
//交换分界值
exch(a,lo,right);
return right;
}
public static void main(String[] args) {
Integer[] a = {4,6,8,7,9,2,10,1};
System.out.println(a);这样输出的是数组的首地址，而不能打印出数组数据
sort(a);
System.out.println(Arrays.toString(a));//此可打印
}
}
package study.sort;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 调用不同的测试方法完成测试(逆排序数据测试)
*/
public class SortComparableEfficiencyTest {
/**
* 冒泡排序
*/
private static void bubbleEfficiency(Integer[] a){
//1. 获取执行前的时间
long start=System.currentTimeMillis();
//2. 执行算法代码
Bubble.sort(a);
//3. 获取执行之后的代码
long end =System.currentTimeMillis();
//4. 算出程序执行的时间并输出
System.out.println("冒泡排序执行的时间为："+(end-start)+"毫秒");
}
/**
* 选择排序
*/
private static void selectionEfficiency(Integer[] a){
//1. 获取执行前的时间
long start=System.currentTimeMillis();
//2. 执行算法代码
Selection.sort(a);
//3. 获取执行之后的代码
long end =System.currentTimeMillis();
//4. 算出程序执行的时间并输出
System.out.println("选择排序执行的时间为："+(end-start)+"毫秒");
}
/**
* 插入排序
*/
private static void insertionEfficiency(Integer[] a){
//1. 获取执行前的时间
long start=System.currentTimeMillis();
//2. 执行算法代码
Insertion.sort(a);
//3. 获取执行之后的代码
long end =System.currentTimeMillis();
//4. 算出程序执行的时间并输出
System.out.println("插入排序执行的时间为："+(end-start)+"毫秒");
}
/**
* 希尔排序
*/
private static void shellEfficiency(Integer[] a){
//1. 获取执行前的时间
long start=System.currentTimeMillis();
//2. 执行算法代码
Shell.sort(a);
//3. 获取执行之后的代码
long end =System.currentTimeMillis();
//4. 算出程序执行的时间并输出
System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒");
}
/**
* 归并排序
*/
private static void mergeEfficiency(Integer[] a){
//1. 获取执行前的时间
long start=System.currentTimeMillis();
//2. 执行算法代码
MergeSort.sort(a);
//3. 获取执行之后的代码
long end =System.currentTimeMillis();
//4. 算出程序执行的时间并输出
System.out.println("归并排序执行的时间为："+(end-start)+"毫秒");
}
/**
* 快速排序
*/
private static void quickEfficiency(Integer[] a){
//1. 获取执行前的时间
long start=System.currentTimeMillis();
//2. 执行算法代码
Quick.sort(a);
//3. 获取执行之后的代码
long end =System.currentTimeMillis();
//4. 算出程序执行的时间并输出
System.out.println("快速排序执行的时间为："+(end-start)+"毫秒");
}
/**
* 效率比较测试
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception{
//1.创建一个ArrayList集合，保存读取出来的整数
ArrayList<Integer> list = new ArrayList<Integer>();
//2.创建缓存读取流BufferReader,读取数据，并缓存到ArrayList中
/*
Class.getClassLoader()是获取当前类的类加载器;
getResourceAsStream()是获取资源的输入流。类加载器默认是从classPath路径加载资源
classpath，顾名思义，就是指 .class 文件所在的路径。.class 文件由 .java 文件编译后产生
classPath:
① src/main/java路径
② src/main/resouces路径
③ 第三方jar包的根路径
*/
BufferedReader reader=new BufferedReader(new InputStreamReader(SortComparableEfficiencyTest.class.getClassLoader().getResourceAsStream("reverse_arr.txt")));
String line;
while ((line=reader.readLine())!=null){
// //line是字符串，把line转换成Integer，存储到集合中
list.add(Integer.valueOf(line));
}
//关闭文件读取
reader.close();
//3.将ArrayList集合转换成数据
//定义一个与数组长度相同的数组
Integer[] a=new Integer[list.size()];
//将list转化成整型数组
list.toArray(a);
//4.调用测试代码完成测试
System.out.println("排序算法效率测试如下：");
//冒泡排序
bubbleEfficiency(a);
//选择排序
selectionEfficiency(a);
//插入排序
insertionEfficiency(a);
//希尔排序
shellEfficiency(a);
//归并排序
mergeEfficiency(a);
//快速排序
quickEfficiency(a);
/**结果如下：
排序算法效率测试如下：
冒泡排序执行的时间为：15796毫秒
选择排序执行的时间为：7043毫秒
插入排序执行的时间为：3毫秒
希尔排序执行的时间为：8毫秒
归并排序执行的时间为：28毫秒
快速排序执行的时间为：3毫秒
*/
}
}
package com.example.java_algorithms.sort;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Demo1 {
/**
* 自己定义的不需要都是static，但是你要在主函数中调用就需要static了，因为main是静态 的
* @param args
*/
public static void main(String args[]){
/**
* 冒泡排序
*/
bubble_sort();
/**
* 选择排序
*/
selection_sort();
/**
* 插入排序
*/
insertion();
}
/**
* 冒泡排序
* 冒泡排序的时间复杂度为 O(n^2)。
* Integer属于包装类，int属于变量
*/
public static void bubble_sort(){
System.out.println(" 冒泡排序:");
int k;
int[] bubble_sort={1,7,5,52,7,55,5,5,879,78,9,6,366,668,666,99,66,5,5,47};
System.out.println(bubble_sort.length);
System.out.println(bubble_sort);
System.out.println("初始："+Arrays.toString(bubble_sort));
if(bubble_sort==null||bubble_sort.length==0){
return ;
}
for (int j=0;j<bubble_sort.length;j++){
for (int i = bubble_sort.length - 1; i > 0; i--) {
if (bubble_sort[i] < bubble_sort[i - 1]) {
k = bubble_sort[i - 1];
bubble_sort[i - 1] = bubble_sort[i];
bubble_sort[i] = k;
System.out.println(Arrays.toString(bubble_sort));
}
}
}
System.out.println("最后结果："+Arrays.toString(bubble_sort));
return;
}
/**
* 选择排序
* 选择排序就是从第一趟开始，用第一个元素和剩下中的每一个元素比较，如果比第一
* 个小，就和第一个元素交换值，最后使得第一个元素中的值最小，第二趟选择出第二
* 小的放到第二元素，依次，使得数组有序
* 排序的时间复杂度为 O(n^2)。
*/
public static void selection_sort(){
System.out.println(" 选择排序:");
int k;
int[] sort={1,7,5,52,7,55,5,5,879,78,9,6,366,668,666,99,66,5,5,47};
System.out.println("初始："+Arrays.toString(sort));
if(sort==null||sort.length==0){
return ;
}
for (int i=0;i<sort.length;i++){
int minIndex = i;
for (int j = i+1; j <sort.length; j++) {
if (sort[minIndex] > sort[j]) {
k = sort[minIndex] ;
sort[minIndex] = sort[j];
sort[j]=k;
System.out.println(Arrays.toString(sort));
}
}
}
System.out.println("最后结果："+Arrays.toString(sort));
return;
}
/**
* 插入排序
* 插入排序是从数组第二个元素开始，找前面的数，比较大小，如果前面的数大
* 就交换位置，然后继续向前比较，。每次从第几个元素开始遍历时都把较
* 小的元素插入到该元素前面，使其前面数组有序，完成一次循环，继续循环下一个元素直至数组有序。
*时间复杂度O（n^2）
*/
public static void insertion(){
System.out.println(" 插入排序:");
int k;
int[] sort={1,7,5,52,7,55,5,5,879,78,9,6,366,668,666,99,66,5,5,47};
System.out.println("初始："+Arrays.toString(sort));
if(sort==null||sort.length==0){
return ;
}
for(int i=0;i<sort.length;i++){
for(int j=i-1;j>=0&&sort[j]>sort[j+1];j--){
k=sort[j];
sort[j]=sort[j+1];
sort[j+1]=k;
}
}
System.out.println(Arrays.toString(sort));
return;
}
}
https://download.csdn.net/download/Tian208/85273570
学习视频网站：（哔哩哔哩）来源：黑马程序员Java数据结构与java算法，全网资料最全数据结构+算法教程
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）