数据结构之排序

数据逻辑结构：
集合
线性关系
树型结构
图状或网状结构

常用内部算法排序

• 选择排序
  1.直接选择排序

原理

直接选择排序过程
直接选择排序过程

实现：

DataWrap.java来模拟待排序的数据

package com.alexanderbai.sort;

public class DataWrap implements Comparable<DataWrap> {
    int data;
    String flag;

    public DataWrap(int data,String flag) {
        this.data = data;
        this.flag=flag;
    }

    @Override
    public String toString() {
        return data + flag;
    }

    //根据data实例变量来决定两个dataWrap的大小
    @Override
    public int compareTo(DataWrap dataWrap) {
        return this.data > dataWrap.data ? 1 : (this.data == dataWrap.data ? 0 : -1);
    }
}

SelectSort.java进行具体的直接选择排序

package com.alexanderbai.sort;

/**
 * @Author AlexanderBai
 * @data 2019/2/6 20:38
 */
public class SelectSort {
    /**
     * 直接选择排序
     * @param dataWraps
     */
    public static void selectSort(DataWrap[] dataWraps) {
        System.out.println("开始排序");
        int arrayLength=dataWraps.length;
        for (int i = 0; i < dataWraps.length - 1; i++) {
            for (int j = i + 1; j < dataWraps.length; j++) {
                if (dataWraps[i].compareTo(dataWraps[j]) > 0) {
                    DataWrap temp = dataWraps[i];
                    dataWraps[i] = dataWraps[j];
                    dataWraps[j]=temp;
                }
            }
            System.out.println(java.util.Arrays.toString(dataWraps));
        }

    }
    /**
     * 直接选择排序（改进）
     * @param dataWraps
     */
    public static void selectSort2(DataWrap[] dataWraps) {
        System.out.println("开始排序");
        int arrayLength=dataWraps.length;
        for (int i = 0; i < dataWraps.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < dataWraps.length; j++) {
                if (dataWraps[i].compareTo(dataWraps[j]) > 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                DataWrap temp = dataWraps[i];
                dataWraps[i] = dataWraps[minIndex];
                dataWraps[minIndex]=temp;
            }
            System.out.println(java.util.Arrays.toString(dataWraps));
        }

    }

    public static void main(String[] args) {
        DataWrap[] dataWrap=new DataWrap[]{
                new DataWrap(10,""), new DataWrap(10,"*"),
                new DataWrap(-10,""),new DataWrap(-10,"*"),
                new DataWrap(100,""),new DataWrap(100,"*"),
                new DataWrap(12,""),new DataWrap(12,"*"),
        };
        System.out.println("排序前:\n"+java.util.Arrays.toString(dataWrap));
        //selectSort(dataWrap);//①
        selectSort2(dataWrap);//②
        System.out.println("排序后：\n"+java.util.Arrays.toString(dataWrap));
    }
}

运行结果一致： 运行结果 分析

2.堆排序

• 交换排序
• 插入排序
• 归并排序
• 桶排序
• 基数排序