1.概述
2.常用排序方法总结
3.冒泡排序
4.选择排序
5.插入排序
6.归并排序
7.快速排序
8.shell排序
1.概述
学过排序算法的朋友可能都知道排序算法有很多种，那在实际应用中我们应该选择哪一种比较恰当呢？当然我们排序算法各有优势
的，在选择的时候也需要我们去衡量，而他的衡量标准就是看该算法的时间复杂度和空间复杂度，所谓的时间复杂度和空间复杂度本质就是
考虑算法在时间效率和内存上的优劣。
2.常用排序方法总结
3.冒泡排序
(1)思路：冒泡排序的思路就是在未排序的序列中从一开始对相邻的两个数依次对比小数往前冒泡，大数向后沉，第一轮结束后最后一个数
的位置已经固定，所以仅仅对前面n-1的数进行第二轮排序，依此类推，最终得到的序列则为有序序列。
(2)Java代码实现：
package com.arithmetic.test;
public class BubbleSort {
/*
* 无参构造方法
*/
public BubbleSort() {
}
/*
* 冒泡排序法
*/
public int[] bubbleSort(int[] array){
int temp;
for (int i = 1; i <= array.length; i++) {
for (int j = 0; j < array.length-i; j++) {
if (array[j]>array[j+1]) {
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
return array;
}
public static void main(String[] args) {
int[] arr ={12,34,56,778,999,445,33,900,34,223,24,567,788,77};
System.out.print("排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
arr = new BubbleSort().bubbleSort(arr);
System.out.print("排序后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
4.选择排序
(1)思路：在乱序数组中假设第一个数位最小，然后依次让后面的数与之对比，一旦有比他小的数就交换他们的位置，一趟下来第一个数就是序列中
最小的一个元素了，然后从第二个元素开始重复上面的操作，最终的到就是有序序列了。
(2)Java代码实现：
package com.arithmetic.test;
public class SelectSort {
public SelectSort() {}
/*
* 选择排序方法
*/
public int[] selectSort(int [] arr){
int minIndex;
int temp;
for (int i = 0; i < arr.length-1; i++) {
minIndex = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[minIndex]>arr[j]) {
temp = arr[j];
arr[j] = arr[minIndex];
arr[minIndex]=temp;
}
}
}
return arr;
}
public static void main(String[] args){
int[] arr ={1,34,56,778,999,445,33,900,34,223,24,567,788,77};
System.out.print("排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
arr = new SelectSort().selectSort(arr);
System.out.print("排序后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
5.插入排序
(1)思路:插入排序的规则就像玩扑克摸牌，每摸一张牌对比一次手上的牌，如果比手上的都大就放到最后面，比手上都小就放到最前面
如果在中间就把比他大的往后移，然后把它插进去，摸完牌后手上的的牌就是有序的了。
(2)Java代码实现：
package com.arithmetic.test;
public class InsertSort {
public InsertSort() {
}
/*
* 插入排序
*
*/
public int[] insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
//value为当前要插入的值
int value = arr[i];
int j=i-1;
//在当前值之前已经排列好的数组中依次对比，如果值都比当前值大，则将当前值后移一位，直到比当前值小或者没有数值为止
while (j>=0&&arr[j]>value) {
arr[j+1] = arr[j];
j--;
}
//将当前要插入的值插入
arr[j+1] = value;
}
return arr;
}
public static void main(String[] args) {
int[] arr ={1,34,56,778,999,445,33,900,34,223,24,567,788,77};
System.out.print("排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
arr = new InsertSort().insertSort(arr);
System.out.print("排序后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
6.归并排序
(1)思路：归并排序就是通过递归的方式将待排序列分成若干个序列，保证每个子序列是有序的，然后再将这些有序的子序列合并
成一个完整的有序序列。
(2)Java代码实现：
package com.arithmetic.test;
public class MergeSort {
public MergeSort() {}
/*
* 归并排序方法
*/
/*public void Sort(int[] arr){
mergeSort(arr, 0, arr.length-1);
}*/
public void mergeSort(int[] arr,int low,int height){
if (low<height) {
//二路归并，将数组拆分成2个数组
int mid = (low+height)/2;
//分别递归调用mergeSort实现排序
mergeSort(arr, low, mid);
mergeSort(arr, mid+1, height);
//最后合并两个有序序列
merge(arr, low, mid, height);
}else {
return;
}
}
public void merge(int[] arr,int low,int mid,int height){
//初始化一个与传入数组相同大小的临时数组
int[] tempArr = new int[arr.length];
//临时数组的索引
int tempIndex = low;
//右边数组的第一个元素下标
int rightOne = mid+1;
//传入需要合并数组的最左边下标，并保存备用
int temp = low;
while (low<=mid && rightOne<=height) {
if (arr[low]<=arr[rightOne]) {
tempArr[tempIndex++]=arr[low++];
}else {
tempArr[tempIndex++]=arr[rightOne++];
}
}
while (low<=mid) {
tempArr[tempIndex++]=arr[low++];
}
while (rightOne<=height) {
tempArr[tempIndex]=arr[rightOne++];
}
while (temp<=height) {
arr[temp] = tempArr[temp++];
}
}
public static void main(String[] args) {
int[] arr ={1000,34,56,778,999,445,33,900,34,223,24,567,788,77};
//int[] arr ={2,4,1,3};
System.out.print("排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
new MergeSort().mergeSort(arr, 0, arr.length-1);
System.out.print("排序后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
7.快速排序
(1)思路:找一个基准值(一半设置为序列第一个),然后让序列元素依次与之对比，将比他小的值放到他左边(前面),将比他大的值放到
他右边(后面),然后再取新序列的第一个元素继续如上操作，依次递归得到最后的有序序列。
(2)Java代码实现：
package com.arithmetic.test;
public class QuickSort {
public QuickSort() {}
public int[] quickSort(int[] arr,int low,int height){
//判斷初始的低位是否比高位低
if (low<height) {
//保存首次循環的低位和高位，一般low=0,height=arr.length-1
int initLow = low;
int initHeight = height;
//設置基準值為數組第一位
int base = arr[low];
while (low<height) {
//從數組最后依次向前與基準值對比,找到第一個比基準值小的數
while (low<height&&arr[height]>=base) {
height--;
}
//將高位值放到低位也就是左邊
if (low<height) {
arr[low++] = arr[height];
}
//從數組的左邊也就是開始位置找到第一個比基準值大的數
while (low<height&&arr[low]<=base) {
low++;
}
//將大的數放到右邊
if (low<height) {
arr[height--]=arr[low];
}
}
//將基準值放到數值中
arr[low]=base;
//遞歸調用對基準數左邊的數組進行排序
quickSort(arr, initLow, low-1);
//遞歸調用對基準數右邊的數組進行排序
quickSort(arr, low+1, initHeight);
}
return arr;
}
public static void main(String[] args) {
int[] arr ={1000,34,56,778,999,445,33,900,34,223,24,567,788,77};
System.out.print("排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
arr = new QuickSort().quickSort(arr, 0, arr.length-1);
System.out.print("排序后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
8.shell排序
(1)思路:初始化一个步长step（一般为长度的一半），然后对相隔长度为step的数组成的若干数组进行插入排序，然后将初始的step
折半，再进行相同的操作,直到step<1为止。
(2)Java实现代码：
package com.arithmetic.test;
public class ShellSort {
public ShellSort() {}
/*
* 希尔排序方法
*/
public void shellSort(int[] arr){
int step = arr.length/2;
while (step>=1) {
for (int i = step; i < arr.length; i++) {
//需要插入的值
int value = arr[i];
//前一个插入值的索引下标
int j =i-step;
//如果存在前一个值，并且大于需要插入的值
while (j>=0&&arr[j]>value) {
//就将前一个插入的值后移一位
arr[j+step]=arr[j];
//循环对比判断插入当前值之前插入值得大小，并作出相应的处理
j-=step;
}
//arr[i]=value;
//这里不能用arr[i]=value虽然从一开始j =i-step看起来j+step=i，但是后面在内层循环中j是在变化的，而i没变
arr[j+step] = value;
}
//步长缩小半
step=step/2;
}
}
public static void main(String[] args) {
int[] arr ={1,34,56,778,999,445,33,900,34,223,24,567,788,77};
System.out.print("排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
new ShellSort().shellSort(arr);
System.out.print("排序后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
ps：排序算法就先总结一点常见的算法类型，其他的后面时间比较充足的时候再学习