数据结构-排序

冒泡排序

/**
 * 冒泡排序
 * 2 5 1 4 3 7 8 9 6
 * 2 1 4 3 5 7 6 8 9
 */
public class PopSort implements Sort{
    public int[] sort(int[] data){
        for (int i = 0; i < data.length; i++) {
            //每次循环将最大的元素移动到数组末尾
            boolean hasMoved = false;
            for (int j = 0; j < data.length-i-1; j++) {
                if (data[j]>data[j+1]){
                    hasMoved = true;
                    int temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }
            }
            if (!hasMoved){
                System.out.println("提前退出:"+i);
                break;
            }
        }
        return data;
    }
}

插入排序

直接插入

/**
* 插入排序
* 2 5 1 4 3 7 8 9 6
* 2 5 1 4 3 7 8 9 6
* 1 2 5 4 3 7 8 9 6
*/
public class InsertSort implements Sort{
   //依次遍历每个元素并插入前面已排序的元素中
   public int[] sort(int[] data) {
       for (int i = 0; i < data.length; i++) {
           int index = i;
           int temp = data[i];
           while (--index>=0){
               if (data[index]>temp){
                   data[index+1] = data[index];
               } else {
                   break;
               }
           }
           data[index+1] = temp;
       }
       return data;
   }

}

二分法插入排序

/**
 * 二分法插入排序
 * 插入数据时使用二分法查找插入位置
 * 2 5 1 4 3 7 8 9 6
 */
public class BinaryInsertSort implements Sort{
    public int[] sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int temp = data[i];
            int left = 0;
            int right = i-1;
            int mid;
            //left 即元素插入的位置
            while (left<=right){
                mid = (left+right)/2;
                if (temp>data[mid]){
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }
            //将插入位置后面的所有元素向后移动
            for (int j = i - 1; j >= left ; j--) {
                data[j+1] = data[j];
            }
            data[left] = temp;
        }
        return data;
    }
}

选择排序


/**
 * 选择排序
 * 2 5 1 4 3 7 8 9 6
 * 1{5 2 4 3 7 8 9 6}
 * 1 2{5 4 3 7 8 9 6}
 * 1 2 3{4 5 7 8 9 6}
 * -----------------
 * 1 2 3 4 5 6 7 8 9
 */
public class SelectSort implements Sort{
    public int[] sort(int[] data){
        for (int i = 0; i < data.length; i++) {
            int minIndex = i;
            for (int j = i; j < data.length; j++) {
                if (data[j]<data[minIndex]){
                    minIndex = j;
                }
            }
           if(i!=minIndex){
            int temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
          }
        }
        return data;
    }
}

希尔排序

/**
 * 希尔排序
 * 2 5 1 4 3 7 8 9 6
 * 1.根据步进长度选出待排序的数组
 * 2.使用冒泡排序对待排序数组排序
 * 3.修改步进长度
 */
public class HeerSort implements Sort{
    public int[] sort(int[] data) {
        //步进长度
        int d = data.length/2;
        while (d>=1){
            for (int i = 0; i <= d; i++) {
                //选出这一组中所有需要排序的数据
                for (int j = i; j < data.length; j+=d) {
                    //冒泡排序这一组数据
                    for (int k = j; k + d < data.length; k+=d) {
                        if (data[k]>data[k+d]){
                            int temp = data[k];
                            data[k] = data[k+d];
                            data[k+d] = temp;
                        }
                    }
                }
            }
            //修改步进长度重新排序
            d = d /2;
            System.out.println("---"+d);
        }
        return data;
    }
}

堆排序

package com.execlib.sort;

/**
 * 堆排序
 *
 * 建堆-调整堆
 */
public class HeapSort implements Sort{
    public int[] sort(int[] data) {
        //建堆最后一个非终端节点开始往上遍历创建大顶堆堆
        for (int i = (data.length-2)/2; i >= 0 ; i--) {
            buildHeap(data,i,data.length-1);
        }
        swapData(data,0,data.length-1);
        //调整堆并取出最大的数字插到数组末尾
        for (int i = data.length-2; i >0; i--) {
            buildHeap(data,0,i);
            swapData(data,0,i);
        }
        return data;
    }
    private void swapData(int[] data,int i,int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    /**
     * 重建堆
     * @param data
     * @param s
     * @param e
     */
    private void buildHeap(int[] data, int s, int e) {
        if (s==e)
            return;
        //调整节点和子节点间的关系
        int tmp = data[s];
        for (int k = 2*s+1; k <= e; k=2*k+1) {
            //k k+1都是s的子节点
            if (k+1<=e&&data[k]<data[k+1]){
                k++;
            }
            //父节点大于子节点中最大的子节点
            if (tmp>data[k]){
                break;
            }
            data[s] = data[k];
            s = k;
        }
        data[s] = tmp;
    }
}

快速排序

package com.execlib.sort;

/**
 * 快速排序
 */
public class QuickSort implements Sort{

    public int[] sort(int[] data) {
        //选取基数 比较数组中每一个元素，大于该基数则将该元素往后挪，小于该基数将元素往前挪
        quickSort(data,0,data.length-1);
        return data;
    }

    private void quickSort(int[] data, int low, int high) {
        if (low>=high)
            return;
        int pivot = data[low];
        int m = getPivotIndex(data,low,high,pivot);
        //将数据分为两部分分开排序
        quickSort(data,low,m-1);
        quickSort(data,m+1,high);
    }

    /**
     * 将基数移动到应该在的位置，并返回基数的位置
     * @param data
     * @param low
     * @param high
     * @param pivot
     * @return
     */
    private int getPivotIndex(int[] data, int low, int high,int pivot) {
        while (low<high){
            while (low<high&&data[high]>pivot){
                high--;
            }
            //将该元素交换到低位
            data[low] = data[high];
            while (low<high&&data[low]<pivot){
                low++;
            }
            //将该元素交换到高位
            data[high] = data[low];
        }
        data[low] = pivot;
        return low;
    }
}

归并排序

package com.execlib.sort;

/**
 * 归并排序
 * 递归排序二分的每一部分然后调用合并函数合并
 */
public class MergeSort implements Sort{

    public int[] sort(int[] data) {
        mergeSort(data,0,data.length-1);
        return data;
    }

    private void mergeSort(int[] data, int low, int high) {
        if (low>=high)
            return;
        int mid = (low+high)/2;
        mergeSort(data,low,mid);
        mergeSort(data,mid+1,high);
        merge(data,low,high,mid);
    }

    private void merge(int[] data, int low, int high, int mid) {
        if (low>=high)
            return;
        int[] tmpArr = new int[high - low + 1];
        int cur1 = low;
        int cur2 = mid+1;
        int i = 0;
        while (cur1<=mid&&cur2<=high){
            if (data[cur1]<data[cur2]){
                tmpArr[i++] = data[cur1++];
            }else {
                tmpArr[i++] = data[cur2++];
            }
        }
        while (cur1<=mid){
            tmpArr[i++] = data[cur1++];
        }
        while (cur2<=high){
            tmpArr[i++] = data[cur2++];
        }
        for (int j = 0; j <i ; j++) {
            data[low+j] = tmpArr[j];
        }
    }

}

基数排序

package com.execlib.sort;

import java.util.ArrayList;
import java.util.List;

public class BasicSort implements Sort{
    public int[] sort(int [] array){
        int max = 0;//��ȡ���ֵ
        for(int i = 0;i<array.length;i++){
            if(max<array[i]){
                max = array[i];
            }
        }
        int times = 0;//��ȡ���ֵλ��
        while(max>0){
            max = max/10;
            times++;
        }
        List<ArrayList> queue = new ArrayList<ArrayList>();//������
        for(int i = 0;i<10;i++){
            ArrayList q = new ArrayList<ArrayList>();
            queue.add(q);
        }
        for(int i = 0;i<times;i++){
            for(int j = 0;j<array.length;j++){
                //��ȡ��Ӧ��λ��ֵ��iΪ0�Ǹ�λ��1��10λ��2�ǰ�λ��
                int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                ArrayList q = queue.get(x);
                q.add(array[j]);//��Ԫ����ӽ���Ӧ�±�����
//              queue.set(x,q);//����
            }
            //��ʼ�ռ�
            int count = 0;
            for(int j = 0;j<10;j++){
                while(queue.get(j).size()>0){
                    ArrayList<Integer> q = queue.get(j);//�õ�ÿһ������
                    array[count] = q.get(0);
                    q.remove(0);
                    count++;
                }
            }
        }
        return array;
    }
    
    public static void main(String[] args){
        BasicSort basicSort = new BasicSort();
        int [] a = {136,2,6,8,9,2,8,11,23,56,34,90,89,29,145,209,320,78,3};
        basicSort.sort(a);
        for(int n:a){
            System.out.print(" "+n);
        }
    }
}

测试用例

package com.execlib.sort;

import java.util.ArrayList;
import java.util.Random;

public class SortTest {
        public static void main(String[] args) {
            //int[] ints = {2, 5, 1, 4, 3, 7, 8, 9, 6};
           //构建数据集
           int[] ints = new int[20];
            ArrayList<Integer> dataList = new ArrayList();
            for (int i = 0; i < ints.length; i++) {
                dataList.add(i);
            }
            Random random = new Random();
            for (int i = 0; i < ints.length; i++) {
                ints[i] = dataList.remove(random.nextInt(dataList.size()));
            }
            Sort sort = null;
            //sort = new SelectSort();
            //sort = new PopSort();
            //sort = new InsertSort();
            //sort = new BinaryInsertSort();
            //sort = new HeerSort();
            //sort = new HeapSort();
            //sort = new QuickSort();
            sort = new MergeSort();
            for (int temp:sort.sort(ints)) {
                System.out.println(temp);
            }
        }

}
  • 测试结果
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。