Java版排序算法

网上很多Java排序算法有错误,以下是本人经过整理校验后的算法。

1、冒泡排序

public class BubbleSort {
    public static void bubbleSort(int[] data) {
        int temp = 0;
        int len = data.length;
        for (int i = 0; i < len - 1; i++) { //最多n-1趟,最后一个元素不用排
            for (int j = len - 1; j > i; j--) {
                if (data[j] < data[j - 1])  //交换两数位置
                {
                    temp = data[j];
                    data[j] = data[j - 1];
                    data[j - 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        bubbleSort(values);
        System.out.println(Arrays.toString(values));
    }
}

2、快速排序

public class QuickSort {
    /**
     * 查找出中轴(默认是最低位low)的在numbers数组排序后所在位置
     *
     * @param data 带查找数组
     * @param low  开始位置
     * @param high 结束位置
     * @return 中轴所在位置
     */
    public static int getMiddle(int[] data, int low, int high) {
        int mid = data[low]; //数组的第一个作为中轴
        while (low < high) {
            while (low < high && data[high] > mid) {
                high--;
            }
            data[low] = data[high];//比中轴小的记录移到低端
            while (low < high && data[low] < mid) {
                low++;
            }
            data[high] = data[low]; //比中轴大的记录移到高端
        }
        data[low] = mid; //中轴记录到尾
        System.out.println("low:"+low + " hight:"+high);
        return low; // 返回中轴的位置
    }

    /**
     * @param data 带排序数组
     * @param low     开始位置
     * @param high    结束位置
     */
    public static void sort(int[] data, int low, int high) {
        if (low < high) {
            int middle = getMiddle(data, low, high); //将numbers数组进行一分为二
            sort(data, low, middle - 1);   //对低字段表进行递归排序
            sort(data, middle + 1, high); //对高字段表进行递归排序
        }

    }

    /**
     * 快速排序
     *
     * @param numbers 带排序数组
     */
    public static void quickSort(int[] data) {
        if (data.length > 0)   //查看数组是否为空
        {
            sort(data, 0, data.length - 1);
        }
    }

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        quickSort(values);
        System.out.println(Arrays.toString(values));
    }
}

3、选择排序

public class SelectSort {
     /**
     * 选择排序算法
     * 在未排序序列中找到最小元素,存放到排序序列的起始位置
     * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。
     * 以此类推,直到所有元素均排序完毕。
     * @param numbers
     */
    public static void selectSort(int[] numbers)
    {
        int len = numbers.length; //数组长度
        int temp = 0 ; //中间变量

        for(int i = 0 ; i < len ; i++)
        {
            int k = i;   //待确定的位置
            //选择出应该在第i个位置的数
            for(int j = len -1 ; j > i ; j--)
            {
                if(numbers[j] < numbers[k]) //找出最小的位置
                {
                    k = j;
                }
            }
            //交换两个数
            temp = numbers[i];
            numbers[i] = numbers[k];
            numbers[k] = temp;
        }
    }

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        selectSort(values);
        System.out.println(Arrays.toString(values));
    }
}

4、堆排序

public class HeapSort {
    /**
     * 构建大根堆
     */
    public static void adjustHeap(int[] data, int i, int len) {
        int temp, j;
        temp = data[i];
        for (j = 2 * i + 1; j < len - 1; j = j * 2 + 1) {// 沿关键字较大的孩子结点向下筛选
            if (j < len - 1 && data[j] < data[j + 1])
                j++; //取左右孩子最大值的下标
            if (temp < data[j]) {
                data[i] = data[j];
                i = j;
            } else //调整结束
                break;
        }
        data[i] = temp;
    }

    public static void heapSort(int[] data) {
        int i;
        int len = data.length;
        for (i = len / 2 - 1; i >= 0; i--) {// 构建一个大根堆
            adjustHeap(data, i, len);
        }
        for (i = len - 1; i >= 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            adjustHeap(data, 0, i);// 将a中前i个记录重新调整为大根堆
        }
    }

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        heapSort(values);
        System.out.println(Arrays.toString(values));
    }

}

5、插入排序

public class InsertSort {
    /**
     * 插入排序
     * <p>
     * 从第一个元素开始,该元素可以认为已经被排序
     * 取出下一个元素,在已经排序的元素序列中从后向前扫描
     * 如果该元素(已排序)大于新元素,将该元素移到下一位置
     * 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
     * 将新元素插入到该位置中
     * 重复步骤2
     *
     * @param data 待排序数组
     */
    public static void insertSort(int[] data) {
        int len = data.length;
        int temp = 0;
        int j = 0;

        for (int i = 0; i < len; i++) {
            temp = data[i];
            //假如temp比前面的值小,则将前面的值后移
            for (j = i-1; j >= 0 && temp < data[j]; j--) {
                data[j+1] = data[j];
            }
            data[j+1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        insertSort(values);
        System.out.println(Arrays.toString(values));
    }
}

6、希尔排序

public class ShellSort {
    public static void shellSort(int[] data) {
        // i表示希尔排序中的第n/2+1个元素(或者n/4+1)
        // j表示希尔排序中从0到n/2的元素(n/4)
        // r表示希尔排序中n/2+1或者n/4+1的值
        int i, j, temp;
        // 划组排序
        int length = data.length;
        int gap = length / 2;
        while (gap >= 1) {
            //每个序列的步长应该是gap,多个序列和在一起执行了,因为算法都一样
            for (i = gap; i < length; i++) { 
                temp = data[i]; //待插入元素
                // 一轮排序
                for (j = i - gap; j >= 0 && temp < data[j]; j -= gap) {
                    data[j + gap] = data[j]; //元素后移
                }
                data[j + gap] = temp; //插入
            }
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        shellSort(values);
        System.out.println(Arrays.toString(values));
    }
}

7、归并排序

    public static int[] sort(int[] data, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            sort(data, low, mid);
            // 右边
            sort(data, mid + 1, high);
            // 左右归并
            merge(data, low, mid, high);
        }
        return data;
    }

    /**
     * 将数组中low到high位置的数进行排序
     * @param data 待排序数组
     * @param low 待排的开始位置
     * @param mid 待排中间位置
     * @param high 待排结束位置
     */
    public static void merge(int[] data, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (data[i] < data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = data[i++];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = data[j++];
        }

        // 把新数组中的数覆盖data数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            data[k2 + low] = temp[k2];
        }
    }

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

    public static void main(String[] args) {
        int[] values = {100, 23, 11, 78, 98, 34, 15, 90, 88, 45, 74, 56};
        mergeSort(values);
        System.out.println(Arrays.toString(values));
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,937评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,503评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,712评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,668评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,677评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,601评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,975评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,637评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,881评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,387评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,971评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2 342

推荐阅读更多精彩内容

  • 概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的...
    Luc_阅读 2,253评论 0 35
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,164评论 0 52
  • 该系列文章主要是记录下自己暑假这段时间的学习笔记,暑期也在实习,抽空学了很多,每个方面的知识我都会另起一篇博客去记...
    Yanci516阅读 12,173评论 6 19
  • 越长大越发现,生活是自己的,与他人无关,与客观条件无关。到最后,你失去的是时间,你经历的是时间的考验,你得到的是遇...
    Cherry小丸子咯阅读 194评论 0 0
  • 回来的路上,表妹跟男友说分手,“什么事哭一场就好了”! 忽然想好像什么事逃不过一场结束!
    忘尘memory阅读 124评论 0 0