1. 冒泡排序：
思路：假设我们要对一个长度为10的数组进行排序，首先进行第一趟排序，第0个元素和第1个元素进行比较，然后第1个元素和第2个元素进行比较，然后第2个元素和第3个元素进行比较，以此类推，直到第8个元素和第9个元素进行比较，此时第一趟排序完毕，数组中最大值被排到第9个元素；第二趟排序，依旧从第0个元素开始，第0个元素和第1个元素进行比较，...，直到第7个元素和第8个元素进行比较，此时第二趟排序完毕，以此类推，总共需要9趟。
- 我们用 i 表示外层循环，控制排序的趟数，用 j 表示内层循环，控制数据之间的比较。java实现如下：
package 冒泡排序;
import java.util.Scanner;
public class BubbleSort {
public static void main(String[] args) {
int temp=0;
System.out.println("请输入排序前的元素：");
Scanner sc=new Scanner(System.in);
int[] sort=new int[10];
//利用sort数组存储从键盘输入的数字
for(int i=0;i<sort.length;i++){
sort[i]=sc.nextInt();
}
//冒泡开始
for(int i=0;i<sort.length-1;i++){
for(int j=0;j<sort.length-i-1;j++){
if(sort[j]>sort[j+1]){
temp=sort[j];
sort[j]=sort[j+1];
sort[j+1]=temp;
}
}
}
//输出排序后的数组
for(int i=0;i<sort.length;i++){
System.out.print(sort[i]+" ");
}
}
}
2. 插入排序（直接插入）
下图是排序过程：
charu.png
代码如下：
package 插入排序;
import java.util.Scanner;
public class InsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int temp=0;
System.out.println("请输入排序前的元素：");
Scanner sc=new Scanner(System.in);
int[] sort=new int[10];
//利用sort数组存储从键盘输入的数字
for(int i=0;i<sort.length;i++){
sort[i]=sc.nextInt();
}
//插入开始
for(int i=0;i<sort.length-1;i++){
for(int j=i+1;j>0;j--){
if(sort[j]<sort[j-1]){
temp=sort[j-1];
sort[j-1]=sort[j];
sort[j]=temp;
}
}
}
//输出排序后的数组
for(int i=0;i<sort.length;i++){
System.out.print(sort[i]+" ");
}
}
}
3. 希尔排序:
原理：是对直接插入排序的一种优化，通过设置一个间隔d，将整个待排序序列分割成若干个子序列，在子序列中进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
下图是希尔排序过程示例：
希尔排序.png
java代码实现如下：
package 希尔排序;
import java.util.Scanner;
public class ShellSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort = new int[10];
inputArr(sort);
shellSort(sort);
printArr(sort);
}
public static void shellSort(int[] sort) {
int j = 0;
int temp = 0;
//设置间隔d
for (int d = sort.length / 2; d > 0; d /= 2) {
//排序开始
for (int i = d; i < sort.length; i++) {
temp = sort[i];
for (j = i - d; j >= 0; j -= d) {
if (temp < sort[j]) {
sort[j + d] = sort[j];
} else {
break;
}
}
sort[j + d] = temp;
}
}
}
public static void inputArr(int[] sort){
System.out.println("请输入排序前的元素：");
Scanner sc = new Scanner(System.in);
for (int i = 0; i < sort.length; i++) {
sort[i] = sc.nextInt();
}
}
public static void printArr(int[] sort){
for(int i=0;i<sort.length;i++){
System.out.print(sort[i]+" ");
}
}
}
4. 快速排序
原理：快速排序是对冒泡排序的一种改进,首先选择序列中第一个记录为轴值，然后进行以下操作，就完成了一趟排序：
- 第一步：将 i ， j 分别指向待排序序列的最左侧和最右侧的记录（也就是序列的第一个元素和最后一个元素）
- 第二步：重复以下操作，直到 i = j
（1）从右侧开始扫描，直到 j 所指向的记录小于轴值，如果存在，则交换两个值，并 i ++
（2）从左侧开始扫描，直到 i 所指向的记录大于轴值，如果存在，则交换两个值，并 j -- - 第三步：返回轴值所在的位置
下面是快速排序一次划分的过程示例图：
快速排序.png
java代码实现如下：
package 快速排序;
import java.util.Scanner;
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort=new int[10];
//从键盘录入元素
inputArr(sort);
quickSort(sort,0,sort.length-1);
System.out.println("排序后的序列：");
printArr(sort);
}
//快速排序一次划分算法
public static int Partition(int[] sort,int low,int high){
int key=sort[low];
while(low<high){
//从右侧开始扫描
while(key<sort[high]){
high--;
}
if(key>sort[high]){
int temp=key;
key=sort[high];
sort[high]=temp;
}
//从左侧开始扫描
while(sort[low]<key){
low++;
}
if(sort[low]>key){
int temp=key;
key=sort[low];
sort[low]=temp;
}
}
return low;
}
//分治法
public static void quickSort(int[] sort,int low,int high){
if(low<high){
int middle=Partition(sort,low,high);
quickSort(sort,low,middle-1);//对左边子序列进行排序
quickSort(sort,middle+1,high);//对右边子序列进行排序
}
}
//定义一个方法从键盘输入带排序的元素
public static void inputArr(int[] sort){
Scanner sc = new Scanner(System.in);
System.out.println("请输入待排序的元素:");
for(int i=0;i<sort.length;i++){
sort[i]=sc.nextInt();
}
}
//定义一个方法输出数组元素
public static void printArr(int[] sort){
for(int i=0;i<sort.length;i++){
System.out.print(sort[i]+" ");
}
}
}
5. 选择排序
原理：每进行一趟排序，就把当前序列中的最小值放到第 i 个位置上
- 步骤：
（1）将整个记录分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录；
（2）在无序区中选取关键码最小的记录，将它与无序区中的第一个记录交换，使得有序区扩展了一个记录，同时无序区减少了一个记录；
（3）不断重复第二步，直到无序区只剩下一个记录为止。
下面是选择排序过程示意图：
选择排序.png
java代码实现如下：
package 选择排序;
import java.util.Scanner;
public class SelectSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort=new int[10];
inputArr(sort);
selectSort(sort);
System.out.println("排序后的序列为：");
printArr(sort);
}
//选择排序开始
public static void selectSort(int[] sort){
//进行length-1趟排序
for(int i=0;i<sort.length-1;i++){
int index=i;
//排序开始
for(int j=i+1;j<sort.length;j++){
if(sort[index]>sort[j]){
index=j;
}
}
if(index!=i){
int temp=sort[index];
sort[index]=sort[i];
sort[i]=temp;
}
}
}
//从键盘输入待排序序列的值
public static void inputArr(int[] sort){
Scanner sc=new Scanner(System.in);
System.out.println("请输入待排序序列：");
for(int i=0;i<sort.length;i++){
sort[i]=sc.nextInt();
}
}
//输出数组
public static void printArr(int[] sort){
for(int i=0;i<sort.length;i++){
System.out.print(sort[i]+" ");
}
}
}
6. 堆排序
原理：
- 堆的定义：是一棵完全二叉树，而且每个节点的值都大于等于其左右孩子的值（大根堆），或者都小于等于左右孩子（小根堆）。
- 排序的过程：首先将待排序系列的记录构造成一个大根堆，然后将堆定记录移走，继续将剩下的记录再调整成大根堆，如此循环，直到堆中只有一个记录为止。
下图是建立初始堆的过程示意图：
堆排序.png
下图是堆排序过程示意图（只给出了前两趟堆排序的结果）
堆排序.png
java代码实现如下：
package 堆排序;
import java.util.Scanner;
public class HeapSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort = new int[10];
inputArr(sort);
// 调用堆排序方法
heapSort(sort);
System.out.println("排序后的序列为：");
printArr(sort);
}
// 堆排序开始
public static void heapSort(int[] sort) {
for (int i = 0; i < sort.length; i++) {
createMaxHeap(sort, sort.length - 1 - i);
Swap(sort, 0, sort.length - 1 - i);
}
}
// 建立大根堆
public static void createMaxHeap(int[] sort, int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int leftChild = 2 * k + 1;
// 如果leftChild小于lastIndex，即leftChild+1代表的k节点的右子节点存在
if (leftChild < lastIndex) {
// 若右子节点的值较大
if (sort[leftChild] < sort[leftChild + 1]) {
// leftChild总是指向较大子节点的索引
leftChild++;
}
}
// 如果k节点的值小于其较大的子节点的值
if (sort[k] < sort[leftChild]) {
// 交换他们
Swap(sort, k, leftChild);
}
else {
break;
}
}
}
}
// 交换两个值
public static void Swap(int[] sort, int i, int j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
// 从键盘输入数据
public static void inputArr(int[] sort) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入待排序序列：");
for (int i = 0; i < sort.length; i++) {
sort[i] = sc.nextInt();
}
}
// 输出数组
public static void printArr(int[] sort) {
for (int i = 0; i < sort.length; i++) {
System.out.print(sort[i] + " ");
}
System.out.println();
}
}
7. 归并排序（二路归并排序）
原理：首先将待排序的序列分为左右两个相等的子序列，分别将
子序列用归并方法进行排序，然后调用“一次归并算法”Merge，再将两个有序子序列合并成一个含有全部记录的有序序列
下图是二路归并的排序 非递归 示意图：
非递归归并.png
下图是二路归并的排序 递归 示意图：
递归归并.png
java代码 递归 实现如下：
package 归并排序;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort = new int[10];
inputArr(sort);
// 调用归并排序方法
mergeSort(sort,0,sort.length-1);
System.out.println("排序后的序列为：");
printArr(sort);
}
//归并排序开始
public static void mergeSort(int[] sort,int low,int high){
int mid=(low+high)/2;
if(low<high){
//左边
mergeSort(sort,low,mid);
//右边
mergeSort(sort,mid+1,high);
//左右归并
Merge(sort,low,mid,high);
}
}
//一次归并
public static void Merge(int[] sort,int low,int mid,int high){
int i=low;
int j=mid+1;
int k=0;
int[] result=new int[high-low+1];
//将两个子序列中最小值取出来
while(i<=mid&&j<=high){
if(sort[i]<sort[j]){
result[k++]=sort[i++];
}else{
result[k++]=sort[j++];
}
}
// 把左边剩余的数移入数组
while(i<=mid){
result[k++]=sort[i++];
}
// 把右边剩余的数移入数组
while(j<=high){
result[k++]=sort[j++];
}
// 把新数组中的数覆盖sort数组
for(int n=0;n<result.length;n++){
sort[n+low]=result[n];
}
}
// 从键盘输入数据
public static void inputArr(int[] sort){
Scanner sc=new Scanner(System.in);
System.out.println("请输入待排序序列：");
for(int i=0;i<sort.length;i++){
sort[i]=sc.nextInt();
}
}
//输出数组
public static void printArr(int[] sort){
for(int i=0;i<sort.length;i++){
System.out.print(sort[i]+" ");
}
System.out.println();
}
}
8. 基数排序（略）
排序算法时间复杂度总结
算法时间复杂度.png
稳定性总结：
- 稳定的排序：直接插入排序、冒泡排序、归并排序、基数排序
- 不稳定的排序：希尔排序、快速排序、简单选择排序、堆排序
