数据结构之Java排序
排序
术语说明
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度： 一个算法执行所耗费的时间。
- 空间复杂度：运行完一个程序所需内存的大小。
算法总结
算法分类
简单排序
Comparable接口
案例
定义一个学生类student ﹐具有年龄ge和姓名username·两个属性·并通过Comparable接口提供比较
学生类并实现Comparable接口
//通过接口比较年龄大小
@SuppressWarnings("all")
public class Student implements Comparable<Student> {
private String name;
private Integer age;
private String sex;
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
", sex='" + sex + '\'' +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
public String getSex() {
return sex;
}
public void setSex(String sex) {
this.sex = sex;
}
@Override
public int compareTo(Student o) {
return this.getAge()-o.getAge();
}
}
测试类
@SuppressWarnings("all")
public class StudentTest {
public static void main(String[] args) {
Student s1=new Student();
s1.setName("黄晓明");
s1.setAge(36);
s1.setSex("男");
Student s2=new Student();
s2.setName("蔡徐坤");
s2.setAge(25);
s2.setSex("男");
Comparable max = getMax(s1, s2);
System.out.println("较大的是演员"+max);
}
public static Comparable getMax(Comparable a,Comparable b)
{
int result = a.compareTo(b);
if(result>0)
{
return a;
}else
{
return b;
}
}
}
冒泡排序
排序原理：（Bubble）
1.比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2.对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
代码实现
import java.util.Scanner;
/**
* 冒泡排序
*/
@SuppressWarnings("all")
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[5];
System.out.println("请输入五个数字：");
Scanner sc = new Scanner(System.in);
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
shunru(arr);
System.out.print("排序后的结果是");
for (int i = 0; i < arr.length; i++) {
System.out.print(" "+arr[i]);
}
}
public static void shunru(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for(int j=0;j<arr.length-i-1;j++)
{
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.print("第" + (i + 1) + "趟排序:");
for (int i1 = 0; i1 < arr.length; i1++) {
System.out.print(" "+arr[i1]+" ");
}
System.out.println();
}
}
}
效果实现图
选择排序
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定
交换位置后达到排序的目的。
说明:
1.选择排序一共有数组大小-1轮排序
2.每1轮排序，又是一个循环，循环的规则(代码)
2.1先假定当前这个数是最小数
2.2然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3当遍历到数组的最后时，就得到本轮最小数和下标
2.4交换[代码]
图解说明
代码实现
import java.util.Scanner;
/**
* 选择排序
*/
@SuppressWarnings("all")
public class SelectSort {
public static void main(String[] args) {
int[] array = new int[5];
System.out.println("请输入五个数字：");
Scanner sc = new Scanner(System.in);
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
selectSort(array);
System.out.print("排序后的结果是:");
for (int i = 0; i < array.length; i++) {
System.out.print(" " + array[i]);
}
}
public static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
int min = array[i];
for (int j = i + 1; j < array.length; j++) {
if (min > array[j]) {
min = array[j];
minIndex = j;
}
}
if (minIndex != i) {
array[minIndex] = array[i];
array[i] = min;
}
System.out.print("第" + (i + 1) + "趟排序:");
for (int m = 0; m < array.length; m++) {
System.out.print(" "+array[m]);
}
System.out.println();
}
}
}
效果实现图
插入排序
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
图解说明
代码实现
import java.util.Scanner;
/**
* 插入排序
*/
@SuppressWarnings("all")
public class InsertSort {
public static void main(String[] args) {
System.out.println("请输入5个数字：");
int[] arr=new int[5];
Scanner sc=new Scanner(System.in);
for (int i = 0; i < arr.length; i++) {
arr[i]=sc.nextInt();
}
insertSort(arr);
System.out.print("排序后的结果是：");
for (int i = 0; i < arr.length; i++) {
System.out.print(" "+arr[i]);
}
}
public static void insertSort(int[] arr)
{
for (int i = 0; i < arr.length-1; i++) {
int insertVal=arr[i+1];
int insertIndex=i;
while(insertIndex>=0&&insertVal<arr[insertIndex])
{
arr[insertIndex+1]=arr[insertIndex];
insertIndex--;
}
arr[insertIndex+1]=insertVal;
System.out.print("第" + (i) + "趟排序:");
for (int m = 0; m < arr.length; m++) {
System.out.print(" "+arr[m]);
}
System.out.println();
}
}
}
效果实现图
希尔排序
介绍：希尔排序是希尔于1959年提出的排序算法。是一种插入排序，是简单排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
思想：
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解说明
代码实现
import java.util.Scanner;
/**
* 希尔排序
*/
@SuppressWarnings("all")
public class ShellSort {
public static void main(String[] args) {
System.out.println("请输入5个数字：");
int[] arr = new int[5];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
shellSort(arr);
System.out.print("排序后的结果是：");
for (int i = 0; i < arr.length; i++) {
System.out.print(" "+arr[i]);
}
}
public static void shellSort(int[] arr) {
int temp = 0;
int count=0;
for (int gap = arr.length / 2; gap > 0; gap /= 2)//gap代表步长
{
for (int i = gap; i < arr.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if(arr[j]>arr[j+gap])
{
temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
count++;
System.out.print("第" + (count) + "趟排序:");
for (int m = 0; m < arr.length; m++) {
System.out.print(" "+arr[m]);
}
System.out.println();
}
}
}
效果实现图
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
代码实现一
import java.util.Scanner;
/**
* 快速排序
*/
@SuppressWarnings("all")
public class QuickSort {
public static void main(String[] args) {
int[] array = new int[5];
Scanner sc = new Scanner(System.in);
System.out.println("请输入5个数字：");
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
/* quick_sort(array, 0, 4);*/
int low = 0;
int high = array.length - 1;
quickSort(array, low, high);
System.out.print("排序后的结果是：");
for (int i1 = 0; i1 < array.length; i1++) {
System.out.print(" "+array[i1]);
}
}
public static void quickSort(int[] arr, int low, int high) {
if (high - low < 1) {
return;
}
boolean flag = true;
int start = low;
int end = high;
int midValue = arr[low];
while (true) {
if (flag)
{
if(arr[high]>midValue)
{
high--;
}else if(arr[high]<midValue)
{
arr[low]=arr[high];
low++;
flag=false;
}
}else{
if(arr[low]>midValue)
{
arr[high]=arr[low];
high--;
flag=true;
}else if(arr[low]<midValue){
low++;
}
}
if(arr[low]==arr[high])
{
arr[low]=midValue;
break;
}
}
quickSort(arr, start, low - 1);
quickSort(arr, low + 1, end);
}
}
实现二
import java.util.Scanner;
/**
* 快速排序
*/
@SuppressWarnings("all")
public class QuickSort {
public static void main(String[] args) {
int[] array = new int[5];
Scanner sc = new Scanner(System.in);
System.out.println("请输入5个数字：");
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
quickSort(array, 0, array.length - 1);
System.out.print("排序后的结果是：");
for (int i1 = 0; i1 < array.length; i1++) {
System.out.print(" " + array[i1]);
}
}
public static void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int pivot = arr[(left + right) / 2];//pivot中轴值
int temp = 0;
while (l < r) {
while (arr[l] < pivot) {
l += 1;
}
while (arr[r] > pivot) {
r -= 1;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == pivot) {
r -= 1;
}
if (arr[r] == pivot) {
l += 1;
}
}
if (l == r) {
l += 1;
r -= 1;
}
if (left < r) {
quickSort(arr, left, r);
}
if (right > l) {
quickSort(arr, l, right);
}
}
}
效果实现图
归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
图解说明一
图解说明二
代码实现
/**
* 归并排序
*
* @param array
* @return
*/
public static int[] MergeSort(int[] array) {
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
/**
* 归并排序——将两段排序好的数组结合成一个排序数组
*
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
