6、八大内部排序--Java代码

淡淡的烟草味﹌ 2022-07-17 01:47 110阅读 0赞

**八大内部排序：**

![Center][]

**一、直接插入排序：**

![Center 1][]

package algorithm.sort;
    
    /**
     * 插入排序之直接插入排序
     * @author baolibin
     */
    public class _04_insertSort {
    	public static void main(String[] args) {
    		int[] tmpNum={54,23,8,87,56,21,34,17,6,23,4};
    		insertSort insertSort = new insertSort(tmpNum);
    		insertSort.insert_Sort();
    		insertSort.fnPrint();
    	}
    }
    class insertSort{
    	private int[] tmpNum;
    	public insertSort(int[] tmpNum){
    		this.tmpNum=tmpNum;
    	}
    	/**
    	 * 直接插入排序
    	 */
    	public void insert_Sort(){
    		int tmp=0,j=0;
    		for (int i = 1; i < tmpNum.length; i++) {
    //			fnPrint();
    			tmp=tmpNum[i];
    			j=i;
    			while (j>0&&tmpNum[j-1]>tmp) {
    				tmpNum[j]=tmpNum[j-1];
    				j--;
    			}
    			tmpNum[j]=tmp;
    		}
    	}
    	/**
    	 * 打印函数
    	 */
    	public void fnPrint(){
    		for (int i = 0; i < tmpNum.length; i++) {
    			if (i==tmpNum.length-1) {
    				System.out.println(tmpNum[i]);
    			}else {
    				System.out.print(tmpNum[i]+"、");
    			}
    		}
    	}
    }

**二、希尔排序：**

![Center 2][]

package algorithm.sort;
    /**
     * 插入排序之希尔排序
     * @author baolibin
     */
    public class _06_shellSort {
    	public static void main(String[] args) {
    		int[] tmpNum={54,23,8,87,56,21,34,17,6,23,4};
    		shellSort shellSort = new shellSort(tmpNum);
    		shellSort.shell_Sort();
    		shellSort.fnPrint();
    	}
    }
    class shellSort{
    	private int[] tmpNum;
    	public shellSort(int[] tmpNum){
    		this.tmpNum=tmpNum;
    	}
    	/**
    	 * 希尔排序
    	 */
    	public void shell_Sort(){
    		int step=tmpNum.length/2;
    		while (1<=step) {
    			this.fnPrint();
    			//遍历所有得的组
    			for (int i = step; i < tmpNum.length; i++) {
    				int j=i-step;
    				//保存要插入的数据
    				int tmp=tmpNum[i];
    				while(j>=0&&tmp<tmpNum[j]){
    					tmpNum[j+step]=tmpNum[j];
    					j=j-step;
    				}
    				tmpNum[j+step]=tmp;
    			}
    			step=step/2;
    		}
    	}
    	/**
    	 * 打印函数
    	 */
    	public void fnPrint(){
    		for (int i = 0; i < tmpNum.length; i++) {
    			if (i==tmpNum.length-1) {
    				System.out.println(tmpNum[i]);
    			}else {
    				System.out.print(tmpNum[i]+"、");
    			}
    		}
    	}
    }

**三、简单选择排序：**

![Center 3][]

package algorithm.sort;
    /**
     * 选择排序之简单选择排序
     * @author baolibin
     */
    public class _05_selectSort {
    	public static void main(String[] args) {
    		int[] tmpNum={54,23,8,87,56,21,34,17,6,23,4};
    		selectSort selectSort = new selectSort(tmpNum);
    		selectSort.select_Sort();
    		selectSort.fnPrint();
    	}
    }
    class selectSort{
    	private int[] tmpNum;
    	public selectSort(int[] tmpNum){
    		this.tmpNum=tmpNum;
    	}
    	/**
    	 * 简单选择排序
    	 */
    	public void select_Sort(){
    		int tmp=0,index=0;
    		for (int i = 0; i < tmpNum.length-1; i++) {
    			index=i;
    			for (int j = i+1; j < tmpNum.length; j++) {
    				if(tmpNum[index]>tmpNum[j]){
    					index=j;
    				}
    			}
    			tmp=tmpNum[i];
    			tmpNum[i]=tmpNum[index];
    			tmpNum[index]=tmp;
    		}
    	}
    	/**
    	 * 打印函数
    	 */
    	public void fnPrint(){
    		for (int i = 0; i < tmpNum.length; i++) {
    			if (i==tmpNum.length-1) {
    				System.out.println(tmpNum[i]);
    			}else {
    				System.out.print(tmpNum[i]+"、");
    			}
    		}
    	}
    }

**四、堆排序：**

![Center 4][]

![Center 5][]

![Center 6][]

package algorithm.sort;
    /**
     * 选择排序之堆排序
     * @author baolibin
     * 
     * 参考网址：
     * http://www.cnblogs.com/jingmoxukong/p/4303826.html
     * http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html
     */
    public class _02_heapSort {
    	public static void main(String[] args) {
    		int[] tmpNum={32,5,76,9,23,43,12,4,56}; //声明的静态数组
    		heapSort heapsort=new heapSort(tmpNum);
    		heapsort.heapScheduler(tmpNum);
    		heapsort.sortPtint();
    	}
    }
    class heapSort{
    	private int[] tmpNum;
    	public heapSort(int[] tmpNum){
    		this.tmpNum=tmpNum;
    	}
    	/**进行堆调整
    	 * @param tmpNum 数组
    	 * @param parent 选择开始调整的父节点存储的数组下标
    	 * @param length 待排序数组的下标长度
    	 */
    	public void heapAdjust(int[] tmpNum,int parent,int length){
    		//先保存当前父节点的值
    		int tmp=tmpNum[parent];
    		//选取当前父节点的左孩子
    		int child=2*parent+1;
    		while(child<length){
    			//选取右孩子的条件：存在右节点且右节点的值大于左节点的值
    			if (child+1<=length&&tmpNum[child]<tmpNum[child+1]) {
    				child++;
    			}
    			//当父节点的值大于孩子节点的时候，直接结束
    			if (tmp>=tmpNum[child]) {
    				break;
    			}
    			tmpNum[parent]=tmpNum[child];
    			
    			//从孩子节点的左孩子开始继续往下筛选
    			parent=child;
    			child=2*child+1;
    		}
    		tmpNum[parent]=tmp;
    	}
    	
    	public void heapScheduler(int[] tmpNum){
    		//建堆
    		//本程序建立大顶堆，保证所有的父节点都比孩子节点大
    		for(int i=tmpNum.length/2;i>=0;i--){
    			heapAdjust(tmpNum, i, tmpNum.length-1);
    		}
    		sortPtint();
    		//进行排序
    		int tmp=0;
    		for (int i=tmpNum.length-1;i>0;i--) {
    			//最后一个元素和第一个元素进行交换
    			tmp=tmpNum[i];
    			tmpNum[i]=tmpNum[0];
    			tmpNum[0]=tmp;
    			/**
    			 按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
    			然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
    			如此反复，直到交换了R[0]和R[1]为止。
    			 */
    			heapAdjust(tmpNum, 0, i);
    			System.out.println("第"+(tmpNum.length-i)+"趟");
    		}
    	}
    	/**
    	 * 打印堆的数据
    	 * 用数组存储的堆
    	 */
    	public void sortPtint(){
    		for(int i=0;i<tmpNum.length;i++){
    			if(i==tmpNum.length-1){
    				System.out.print(tmpNum[i]);
    			}else {
    				System.out.print(tmpNum[i]+"、");
    			}
    		}
    	}
    }

**五、冒泡排序：**

![Center 7][]

package algorithm.sort;
    /**
     * 交换排序之冒泡排序
     * @author baolibin
     */
    public class _03_bubbleSort {
    	public static void main(String[] args) {
    		int[] tmpNum={54,23,8,87,56,21,34,17,6,23,4};
    		bubbleSort bubbleSort = new bubbleSort(tmpNum);
    		bubbleSort.bullble_Sort();
    		bubbleSort.fnPrint();
    	}
    }
    class bubbleSort{
    	private int[] tmpNum;
    	public bubbleSort(int[] tmpNum){
    		this.tmpNum=tmpNum;
    	}
    	/**
    	 * 冒泡排序函数
    	 */
    	public void bullble_Sort(){
    		int tmp=0;
    		for (int i = 0; i < tmpNum.length-1; i++) {
    			for (int j = i+1; j < tmpNum.length; j++) {
    				if(tmpNum[j]<tmpNum[i]){
    					tmp=tmpNum[i];
    					tmpNum[i]=tmpNum[j];
    					tmpNum[j]=tmp;
    				}
    			}
    		}
    	}
    	/**
    	 * 打印函数
    	 */
    	public void fnPrint(){
    		for (int i = 0; i < tmpNum.length; i++) {
    			if (i==tmpNum.length-1) {
    				System.out.println(tmpNum[i]);
    			}else {
    				System.out.print(tmpNum[i]+"、");
    			}
    		}
    	}
    }

**六、快速排序：**

![Center 8][]

package algorithm.sort;
    /**
     * 8大内部排序算法之一：交换排序之快速排序
     * author：baolibin
     */
    public class _01_quickSort {
    	public static void main(String[] args) {
    		int[] tmpNum={32,12,76,3,9,26,72,9,2,54,3,23}; //待排序的数组
    		Sort sort=new Sort(tmpNum);
    		sort.sortScheduler(0, tmpNum.length-1, tmpNum);
    		sort.print();
    	}
    }
    
    class Sort {
    	private int[] sortTmp;
    	public Sort(int[] sortTmp) {
    		this.sortTmp = sortTmp;
    	}
    	/**
    	 * 递归调用进行排序
    	 * @param low 左指针
    	 * @param hight 右指针
    	 * @param tmpNum 数组
    	 */
    	public void sortScheduler(int low, int hight,int[] tmpNum){
    		if(low<hight){
    			int middle=sortNum(0, hight, tmpNum);
    			if(middle>0&&middle<hight){
    				sortScheduler(0, middle-1, tmpNum);
    				sortScheduler(middle+1, hight, tmpNum);
    			}
    		}
    	}
    	/**
    	 * @param low 左指针
    	 * @param hight 右指针
    	 * @param tmpNum 数组
    	 * @return 基准元素插入的位置
    	 */
    	public int sortNum(int low, int hight, int[] tmpNum) {
    		int tmp = tmpNum[low];
    		while (low < hight) {
    			while (low < hight && tmp <= tmpNum[hight]) {
    				hight--;
    			}
    			tmpNum[low] = tmpNum[hight];
    			while (low < hight && tmpNum[low] <= tmp) {
    				low++;
    			}
    			tmpNum[hight] = tmpNum[low];
    		}
    		tmpNum[low] = tmp;
    		return low;
    	}
    	/**
    	 * 进行结果的打印
    	 */
    	public void print() {
    		for (int i = 0; i < sortTmp.length; i++) {
    			if(i==sortTmp.length-1){
    				System.out.print(sortTmp[i]);
    			}else{
    				System.out.print(sortTmp[i] + "、");
    			}
    		}
    	}
    }

**七、归并排序：**

![Center 9][]

package algorithm.sort;
    /**
     * 归并排序
     * @author baolibin
     */
    public class _07_mergeSort {
    	public static void main(String[] args) {
    		int[] tmpNum={54,23,8,87,56,21,34,17,6,23,4};
    		mergeSort mergesort = new mergeSort(tmpNum);
    		mergesort.sortProgress();
    		mergesort.fnPrint();
    	}
    }
    class mergeSort {
    	private int[] tmpNum;
    	public mergeSort(int[] tmpNum) {
    		this.tmpNum=tmpNum;
    	}
    	/**
    	 * 归并排序
    	 * @param tmpNum 待排序的数组
    	 * @param low 第一段数组的起始下标
    	 * @param middle 第一段数组的末尾下标
    	 * @param high 第二段数组的末尾下标
    	 */
    	public void merge_Sort(int[] tmpNum, int low, int middle, int high) {
    		int first = low; // 存放第一段序列下标
    		int second = middle + 1; // 存放第二段序列下标
    		int tmpkey = 0; // 存放合并数组的下标
    		int tmp[] = new int[high - low + 1]; // 存放合并数组用的
    		while (first <= middle && second <= high) {
    			if (tmpNum[first] < tmpNum[second]) {
    				tmp[tmpkey] = tmpNum[first];
    				first++;
    				tmpkey++;
    			} else {
    				tmp[tmpkey] = tmpNum[second];
    				second++;
    				tmpkey++;
    			}
    		}
    		// 第一个段数组没有遍历完
    		while (first <= middle) {
    			tmp[tmpkey] = tmpNum[first];
    			first++;
    			tmpkey++;
    		}
    		// 第二个段数组没有遍历完
    		while (second <= high) {
    			tmp[tmpkey] = tmpNum[high];
    			second++;
    			tmpkey++;
    		}
    		int k=low;
    		//将合并的数组拷贝到原始的数组中
    		for (int i = 0; i < tmp.length; i++) {
    			tmpNum[k]=tmp[i];
    			k++;
    		}
    	}
    	public void sortProgress(){
    		//进行每趟归并，改变字表的长度
    		for (int step = 1; step < tmpNum.length; step=2*step) {
    			int i=0;
    			//进行每趟归并排序,归并长度为step的两个相邻的子表
    			for(i=0;i+2*step-1<tmpNum.length;i=i+2*step){
    				merge_Sort(tmpNum, i, i+step-1, i+2*step-1);
    			}
    			//剩下单独的一个子表
    			if (i+step-1<tmpNum.length) {
    				merge_Sort(tmpNum, i, i+step-1, tmpNum.length-1);
    			}
    		}
    	}
    	/**
    	 * 打印函数
    	 */
    	public void fnPrint() {
    		for (int i = 0; i < tmpNum.length; i++) {
    			if (i == tmpNum.length - 1) {
    				System.out.println(tmpNum[i]);
    			} else {
    				System.out.print(tmpNum[i] + "、");
    			}
    		}
    	}
    }

**八、基数排序：**

![Center 10][]

package algorithm.sort;
    /**
     * 基数排序
     * @author baolibin
     */
    public class _08_radixSort {
    	public static void main(String[] args) {
    		int[] tmpNum={54,23,8,187,56,21,341,17,6,23,4,88,33,40,39,73,15};
    		radixSort radixsort = new radixSort(tmpNum);
    		radixsort.radix_Sort(tmpNum,3); //开始基数排序
    		radixsort.fnPrint();
    	}
    }
    /**
     * 
     * @author Administrator
     *
     */
    class radixSort{
    	private int[] tmpNum; //带排序的数组
    	private int radix=10; //指0~9,像邻接链表的左侧竖着显示的数组
    	private int[] bucket_offset_right;//一共10位，每个值代表着，在bucket数组，的对应桶，的末尾的下标。 以及每个桶存储的个数
    	private int[] bucket; 原本邻接链表的结构用数组进行存储，每个桶在对应范围下标进行存储。
    	public radixSort(int[] tmpNum) {
    		this.tmpNum=tmpNum;
    		bucket_offset_right=new int[radix]; //代表着每个桶的个数以及在bucket桶数组中的存储下标
    		bucket=new int[tmpNum.length];
    	}
        /**
         *  基数排序部分
         * @param tmpNum 待排序的数组
         * @param low_index 数组的开始下标
         * @param high_index 数组的结尾下标
         * @param max_Num_length 数组中最大元素的位置
         */
        public void radix_Sort(int[] tmpNum,int max_length){
        	for (int i = 1; i <= max_length; i++) {
    			for (int j = 0; j < radix; j++) { //各个桶存储的个数置为0
    				bucket_offset_right[j]=0;
    			}
    			int countNum=0;
    			for (int j = 0; j < tmpNum.length; j++) {  //统计每个桶要装入的数据的个数
    				countNum=tmpNum[j]/((int) Math.pow(10, i-1))%10;
    //				System.out.println("countNum="+countNum);
    				bucket_offset_right[countNum]++;
    			}
    			for (int j = 1; j < radix; j++) { //存储每个桶截止本桶一共装的个数，存的值对应桶数组下标，方便进行每个桶快速定位进行存储
    				bucket_offset_right[j]=bucket_offset_right[j]+bucket_offset_right[j-1];
    			}
    			for (int j = tmpNum.length-1; j >=0; j--) { //将数据依次存入桶中
    				countNum=tmpNum[j]/((int) Math.pow(10, i-1))%10;
    				bucket[bucket_offset_right[countNum]-1]=tmpNum[j];  //将数据存储到对应桶的指定数组位置，倒着进行存储
    				bucket_offset_right[countNum]--; //对应桶存储位置指针，从桶的末尾往前移一位
    			}
    			for (int j = 0; j < tmpNum.length; j++) {
    				tmpNum[j]=bucket[j];
    			}
    //			fnPrint();
    		}
        }
    	/**
    	 * 打印函数
    	 */
    	public void fnPrint() {
    		for (int i = 0; i < tmpNum.length; i++) {
    			if (i == tmpNum.length - 1) {
    				System.out.println(tmpNum[i]);
    			} else {
    				System.out.print(tmpNum[i] + "、");
    			}
    		}
    	}
    }

**八大内部排序的复杂度比较：**

![Center 11][]

[Center]: /images/20220717/059fab9a4acf4ac7bc5285c55aaf7378.png
[Center 1]: /images/20220717/84dd86d4940b4fe1ad5d052d9fcc9e7f.png
[Center 2]: /images/20220717/6a8ae546412949038a1dec435f385296.png
[Center 3]: /images/20220717/29d8fa2c058440de9cfce199e1d11e1c.png
[Center 4]: /images/20220717/454b0712254c49e092c2972f6f6d82d4.png
[Center 5]: /images/20220717/63f6aa7203e04fdbb32ae586a8952936.png
[Center 6]: /images/20220717/791e45a2f6794361b01f3b050c0b43d1.png
[Center 7]: /images/20220717/6c8482b63a114daca60e0fdf65b54296.png
[Center 8]: /images/20220717/e513083393ef4f2caff81b18b0dc60d7.png
[Center 9]: /images/20220717/6c996190eee44b37b4ad734a6db08845.png
[Center 10]: /images/20220717/59fe83539a5b4631ba46894e627f8d90.png
[Center 11]: /images/20220717/995a0f13ae2b4c7ca50ab05d413a89a2.png