不稳定的排序算法：快希选堆
1，算法思路：
2，代码实现：
package com.yzd0507.Order;
//测试几种经典的排序算法
public class Sort {
//1,冒泡排序 从小到大
public void bubbleSort(int[] arr) {
int len = arr.length;
for(int i=0;i<len-1;i++) {
for(int j=0;j<len-1-i;j++) {
if(arr[j]>arr[j+1]) {
int temp = arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
//排序完毕 输出打印元素查看
for(int k=0;k<len;k++) {
System.out.println(arr[k]);
}
}
public static void main(String[] args) {
Sort sort = new Sort();
int[] array= {12,3,2,4,66,32,9,2,43};
sort.bubbleSort(array);
}
}
1，算法思路
2，代码实现
//2,选择排序 从小到大
public void selectSort(int[] arr) {
int len = arr.length;
for(int i=0;i<len-1;i++) {
int minIndex = i;
for(int j=i;j<len;j++) {
if(arr[j]<arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
//排序完毕 输出排序后的数组
for(int k=0;k<len;k++) {
System.out.println(arr[k]);
}
}
int[] array= {12,3,2,4,66,32,9,2,43};
sort.selectSort(array);
1，算法思路
2，代码实现
//3,插入排序 从小到大
public void insertSort(int[] arr) {
int len = arr.length;
for(int i=0;i<len-1;i++) {
int curIndex=i;//当前已排好序的数组的最后一个下标
int temp = arr[i+1];//需要插入排序的元素
while(curIndex>=0&&temp<arr[curIndex]) {//一直比较到已排序序列的第一个元素 并且需要插入的元素小于当前比较的元素
arr[curIndex+1]=arr[curIndex]; //从后往前比较
curIndex--;
}
arr[++curIndex] = temp; //直到比较到第一个已排序的第一个元素 或者 不小于当前元素 此时由于curIndex--
//index已经移位到需要插入的前一位 所以需要先index+1再插入
}
//排序完毕 输出排序后的数组
for(int k=0;k<len;k++) {
System.out.println(arr[k]);
}
}
int[] array= {12,3,2,4,66,32,9,2,43};
sort.insertSort(array);
希尔排序是直接插入排序的一种改进版本，也称缩小增量排序。希尔排序是根据下标的增量对序列进行分组，每组内进行直接插入排序，然后逐步缩小增量，重新插入排序，直到增量缩小为1，整个序列被分为1组，插入排序，算法终止。
1，操作流程：
2，代码实现：
//4,希尔排序 从小到大
public void shellSort(int[] arr) {
int len = arr.length;
for(int gap=len/2;gap>0;gap/=2) {//逐步缩小增量
for(int i=0;i<gap;i++) {//每一个分组 i为每一个分组头下标
//组内插入排序 j为每一组分组元素下标 防止数组下标越界
for(int j=i;j<len&&j+gap<len;j=j+gap) {
int temp = arr[j+gap];//当前需要插入排序的元素
int curIndex=j;//当前已排好序的数组的最后一个下标
while(curIndex>=0&&temp<arr[curIndex]) {//一直比较到已排序序列的第一个元素 并且需要插入的元素小于当前比较的元素
arr[curIndex+gap]=arr[curIndex]; //从后往前比较 将当前元素往后移
curIndex = curIndex-gap;//当前元素组内前移
}
curIndex = curIndex+gap; //找到当前需要插入排序的元素的插入位置
arr[curIndex] = temp;
}
}
}
//排序完毕 输出排序后的数组
for(int k=0;k<len;k++) {
System.out.println(arr[k]);
}
}
int[] array= {12,3,2,4,66,32,9,2,43};
sort.shellSort(array);
归并排序采用分治法，结合递归使用。
1，算法描述
2，操作流程：
对序列：12 ， 3 ， 2 ，4，66，32，9，2，43 进行归并排序，图中绿色字体为每次归并操作的数据，不同长度的红色斜线代表不同层级的分组。
3，代码实现
//5,归并排序
public void mergeSort(int[] arr) {
int len = arr.length;
sort(arr,0,len-1);//归并排序
// for(int i=0;i<arr.length;i++) {//打印排序后的数组
// System.out.println(arr[i]);
// }
}
public void sort(int[] arr,int left,int right) {
if(right-left<1) {
return;//递归退出条件 当每个元素为一组 无法再拆分时
}
int mid = (left+right)/2;
//对左边序列递归归并排序 arr包括左、右两边序列 left、mid、mid+1、right限制了操作数据位置
sort(arr,left,mid);//原左+右原始数组 左边序列起、终下标
//对右边序列递归归并排序
sort(arr,mid+1,right);//原左+右原始数组 右边序列起、终下标
//将左右两边序列合并
merge(arr,left,mid,right);
System.out.print("执行完一次归并后原数组中的数据:");
for(int i=0;i<arr.length;i++) {//打印排序后的数组
System.out.print(arr[i]+" ");
}
System.out.println(" ");
System.out.println(" ");
}
//将左、右两个序列合并
public void merge(int[] arr,int left,int mid,int right) {
//传入的left、mid、right为在最原始序列中的下标
System.out.println("每次合并时left的下标:"+left);
int mid1 = mid+1;
//left为左边序列起始下标 mid为左边序列终止下标 mid2为右边序列起始下标 right为右边序列终止下标
int[] temp = new int[right+1];//用来存放合并后的序列的临时数组 根据需要合并的right位置创造合适的长度
System.out.println("temp的长度:"+temp.length);
int index=left;//临时数组的下标 ???正确方式 不一定从temp数组0下标开始复制可以只在某些位置赋值 其他位置空着为默认值0 在temp数组终对应原数组位置开始复制
//int index=0; //???错误方式 index为左+右 右边序列合并时index是在左边序列的基础上递归增加右边序列的
int lstart=left;//记录左边序列第一个元素的下标 ???正确方式
//int lstart=0;// ???错误方式 中间部分lstart并不是从0开始 是在每个分组对应位置排序 并没有单拎出来排序
int rstart=mid1;//记录右边序列第一个元素的下标
//1,从左、右两边序列的初始位置开始 取较小值放在temp数组中，取了值的序列起始位置后移一位 没取值的不变
while(lstart<=mid&&rstart<=right) {
if(arr[lstart]<arr[rstart]) {
temp[index]=arr[lstart++];
//System.out.println(temp[index]);
index++;
}else {
temp[index]=arr[rstart++];
//System.out.println(temp[index]);
index++;
}
}
//2,当某一边序列全部取完后 直接将另一边剩下的数据复制给temp数组（在上一轮递归中每边序列已经拍好序）
//以下两个if只有一个会执行
while(lstart<=mid) {
temp[index++]=arr[lstart++];
//System.out.println(temp[index]);
}
while(rstart<=right) {
temp[index++]=arr[rstart++];
//System.out.println(temp[index]);
}
//3,将temp中的数据复制到arr中????? 错误方式 每次仅对执行了合并操作的arr更新元素 没有执行合并操作的arr的元素不改变 并不一定从0操作
// //右边递归调用merge方法时是在左边的基础上操作 生成的temp长度为左+右 因此u的起始下标为left(右序列的left)
// for(int u=0;u<temp.length;u++) {
// arr[u]=temp[u];
//
// //System.out.print(temp[u]+" ");
// }
System.out.print("新生成的temp数组中的数据:");
//3,将temp中的数据复制到arr中 ??? 正确方式
for(int u=left;u<temp.length;u++) {//结合创建temp数组长度和初始化index时 即从left位置开始复制
arr[u]=temp[u];
System.out.print(temp[u]+" ");
}
System.out.println(" ");
}
int[] array= {12,3,2,4,66,32,9,2,43};
sort.mergeSort(array);
输出结果图：
以上算法完整代码：
百度网盘提取码：g903