排序详细分析

前言 : 博主之前也是一直很懒 排序的时间复杂度也是都去看别人写的 没有测试过. 今天想想就把代码全部贴出来 C语言和JAVA代码都会贴出来 测试是在JAVA上测试的 而且之前一直没怎么用插入 因为懒就去写冒泡的代码 因为短嘛! 我知道有人和我是一样的哈哈. 如果是写题或者别的干嘛 就会 用C++的algorithm库中的sort 或者 JAVA的 的sort方法. 其实C语言stdlib库中也有qsort方法 有兴趣的去查查. 最近学完了希尔排序 才发现 希尔排序也不是一般的好用 而且代码很好写.所以今天我想把 各种排序的时间都贴出来和大家分享 注意! 我是在JAVA虚拟机上测试出来的.

话不多说 : 先说说测试了什么 

1.简单选择排序

2.冒泡排序

3.插入排序

4.优化的插入排序

5.希尔排序.

6.优化的希尔排序.

7快速排序.

8.归并排序.

9.JAVA的Arrays的sort方法(没学JAVA可以不用管这个)

10.堆排序

先说明 我这里的测试 用了0 - 10005 的随机数

而且所有的排序都是用了同一个随机数数组 也就是9个方法 我复制了9份这样数组

for (int i = 0; i < N; i++) {
            box[i] = rm.nextInt(10005); //这里就是获得一个[0,10005)的随机数
            box2[i] = box[i];
            box3[i] = box[i];
            box4[i] = box[i];
            box5[i] = box[i];
            box6[i] = box[i];
            box7[i] = box[i];
            box8[i] = box[i];
            box9[i] = box[i];
        }

看不懂JAVA的不用去管 知道 这是随机数就好

好了 声明 N 就是我们的测试个数

开始让N为10看一下结果

当N变为100

当N变为1000

两张图 1000的两次结果 为了说明结果

接下来都是两张图

N = 10000

N = 100000

好了 接下来 加0的时候我准备取消几个排序

以免太慢

有一次 我N = 1000000

我出去吃了个饭 冒泡还没跑完

最后 跑了36分钟....

N = 1000000

一激动 放了4张图

N = 10000000

好了 结果已经对比出来了 冒泡 最慢 然后是 简单选择 

然后是插入

当时刚学C语言1个多月的时候去打比赛

当时因为只掌握了冒泡和简单选择 快排不是太熟

怕写不出来 有一道题要用排序 就用了冒泡

因为当时觉得 冒泡应该是插入 冒泡 和 简单选择 

三个排序中最快的

后来发现是最慢的

结果那道题 一直运行超时 真后悔啊

总结 : 数据较少的时候都很快 N = 1000的时候建议用插入

这里说一下 插入的优化 和希尔排序的优化是什么

没有优化的是交换

优化了的是 覆盖 然后最后一次交换

N = 10000的时候 冒泡就开始吃力. 我记得C语言的比赛

时间限制好像是3000ms

插入排序在数据少 有序数据多的情况很不错

数据少的时候不是很建议去使用快排 归并

因为他们都有递归

而且 归并虽然很快 但是有时间开销.

其实我们现在做的无非也就是用时间去换空间

或者用空间去换时间

这里我强烈推荐希尔排序 时间复杂度可以接受

不消耗空间 且写法简单

接下来就是代码

因为用到的语法和C语言很像就说明一下

如果想学习可以去看看别人的算法教学

应该都很详细,我就不讲了哈哈哈...

后面都只写核心代码

1.简单选择排序

for (int i = 0; i < N - 1; i++) {
            int index = i;
            for (int j = i + 1; j < N; j++) {
                if (arr[index] < arr[j]) {
                    index = j;
                }
            }
            int t = arr[i];
            arr[i] = arr[index];
            arr[index] = t;
        }

2.冒泡排序

 for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - i; j++) {
                if(arr[j] > arr[j+1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j+1] = t;
                }
            }
        }

3.插入排序

 for (int i = 1; i < N; i++) {
            int j;
            for (j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                int t = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = t;
            }
        }

4.优化插入排序

for (int i = 1; i < N; i++) {
            int temp = arr[i];
            int j;
            for (j = i;j> 0 && temp < arr[j - 1] ; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }

5.希尔排序(个人最喜欢)

  int n = 1;
        while(n < N/3) n = n*3 + 1;
        while (n >= 1) {
            for (int i = n; i < N; i++) {
                int j;
                for (j = i; j >=n && arr[j] < arr[j-n]; j-=n) {
                    int t = arr[j];
                    arr[j] = arr[j - n];
                    arr[j - n] = t;
                }
            }
            n/=3;
        }

6.优化希尔排序(个人最喜欢)

 int n = 1;
        while(n < N/3) n = n*3 + 1;
        while (n >= 1) {
            for (int i = n; i < N; i++) {
                int j;
                int temp = arr[i];
                for (j = i; j >=n && temp < arr[j-n]; j-=n) {
                    arr[j] = arr[j - n];
                }
                arr[j] = temp;
            }
            n/=3;
        }

7.快速排序

因为用到函数递归所以函数声明也写

C语言把前面public static 去掉即可

public static void sort(int[] arr, int left, int right) { 
        if (left > right) {
            return ;
        }
        int i = left, j = right, temp = arr[left], t;
        while (i != j) {
            while (arr[j] >= temp && i < j) {
                j--;
            }
            while (arr[i] <= temp && i<j) {
                i++;
            }
            if (i < j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[left] = arr[i];
        arr[i] = temp;
        sort(arr, left, i - 1);
        sort(arr, i+1, right);
    }

8.归并排序

因为用到函数递归所以函数声明也写

C语言把前面public static 去掉即可

下文分配空间C语言可以在合并函数里分配一个辅助空间

大小满足r-l+1就行

直接定义 或者malloc(用完释放)都可以

 public static int[] temp = new int[N]; //这是分配空间的 
    public static void sort(int[] arr,int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r)/2;
        sort(arr, l, mid);
        sort(arr, mid+1, r);
        marge(arr,l, mid, r);
    }

    public static void marge(int[] arr, int l,int mid, int r) {
        int i = l, j = mid+1;

        for (int k = l; k <= r; k++) {
            temp[k] = arr[k];
        }

        for (int k = l; k <= r; k++) {
            if(i > mid) arr[k] = temp[j++];
            else if(j > r) arr[k] = temp[i++];
            else if(temp[j] < temp[i]) arr[k] = temp[j++];
            else arr[k] = temp[i++];
        }

    }

10.归并排序

因为用到函数递归所以函数声明也写

C语言把前面public static 去掉即可

 public static void sort(int[] arr) {
        for (int i = (N - 1) /2 -1; i >= 0; i--)
            sink(arr,i,N-1);
        int n = N - 1;
        while (n > 0) {
            int t = arr[0]; arr[0] = arr[n]; arr[n] = t;
            n--;
            sink(arr, 0, n);
        }
    }
    public static void sink(int[] arr, int k, int n) {
        while (2 * k + 1 <= n) {
            int j = 2*k +1 ;
            if (j+1 <= n && arr[j] < arr[j + 1]) j++;
            if (arr[k] > arr[j]) break;
            int t = arr[j]; arr[j] = arr[k]; arr[k] = t;
            k = j;
        }
    }

个人认为 几种排序的排名

理解难易度 选择 < 冒泡 < 插入 < 归并 < 快排 = 希尔 < 堆排

写法难易度 选择= 冒泡 < 插入 < 希尔 <快排 < 归并 <= 堆排

归并和堆排的写法上小细节太多 容易出错 

我在写的时候就出了几个小错误 导致错误的排序

注意点就好了

好了就到这里.有兴趣的搜一下算法赶快get起来吧哈哈