你好,游客 登录 注册 搜索
背景:
阅读新闻

数据结构中的7种排序算法

[日期:2016-04-01] 来源:CSDN博客  作者:Decorator2015博客 [字体: ]

数据结构中的7种排序算法

排序是将一个记录的任意序列重新排列成一个按键值有序的序列。

时间复杂度主要考虑元素的移动次数。

结构如下:

1.直接插入排序

1,定义:依次将待排序序列中的每一个记录插入到一个已经排好序的序列中,直到全部记录都排好序。

2,时间复杂度:在最好情况下,待排序序列为正序,时间复杂度为O(n);最坏情况下,待排序序列为逆序,时间复杂度为O(n^2);平均情况下,时间复杂度为O(n^2)。

3,空间复杂度:O(1)。

public static void insertSort(int[] nums){//直接插入排序

        for(int i=1;i<nums.length;i++){
            for(int j=i;j>0;j--){
                if(nums[j]<nums[j-1]){                  
                    int temp=nums[j];
                    nums[j]=nums[j-1];
                    nums[j-1]=temp; 
                }   

            }

            System.out.print(i+":");
            for(int a:nums) 
                System.out.print(a+" ");
            System.out.println();
        }

    }

示例数组:{12,5,9,20,6,31,24} 结果:

2.希尔排序

1,希尔排序是对直接插入排序的改进。

2,定义:先将整个待排序序列记录序列分割为若干个子序列,在子序列内分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。

3,时间复杂度:O(nlogn)~O(n^2)。

4,空间复杂度:O(1).

public static void shellSort(int[] nums){//希尔排序

        int d=nums.length/2;//增量大小
        while(d>0){

            int k=0;//控制量
            while(k<d){

                //进行直接插入排序
                for(int i=k;i<nums.length;i=i+d){
                    for(int j=i;j>0&&j-d>=0;j=j-d){
                        if(nums[j]<nums[j-d]){                  
                            int temp=nums[j];
                            nums[j]=nums[j-d];
                            nums[j-d]=temp; 
                        }                       
                    }                   
                }   

             k++;//控制量增加

            }//while

            System.out.print(d+":");
            for(int a:nums) 
                System.out.print(a+" ");
            System.out.println();

            d=d/2;

         }//while
    }

示例数组:{12,5,9,20,6,31,24} 结果:

3.冒泡排序

1,定义:两两比较相邻记录的关键码,如果是反序则交换,直到没有反序的记录为止。

2,时间复杂度:在最好情况下,待排序序列为正序。其时间复杂度为O(n);在最坏情况下,待排序序列为逆序,时间复杂度为O(n^2),平均时间复杂度为O(n^2).

3,空间复杂度:O(1)。

public static void bubbleSort(int[] nums){//冒泡排序
        for(int i=nums.length-1;i>0;i--){

            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
            System.out.print(nums.length-i+":");
            for(int a:nums) 
                System.out.print(a+" ");
            System.out.println();
        }

    }

示例数组:{12,5,9,20,6,31,24} 结果:

4.快速排序

1,快速排序是对冒泡排序的改进。

2,定义:首先选一个轴值,将待排序记录分割成独立的两部分,左侧记录的关键字均小于或者等于轴值,右边记录的关键字均大于或者等于轴值,然后分别对这两部分重复上述过程,直到整个序列有序。

3,在最好情况下,每次划分轴值的左侧子序列与右侧子序列的长度相同,时间复杂度为O(nlogn),在最坏情况下,待排序序列为正序或逆序,时间复杂度为O(n^2);平均情况下,时间复杂度为O(nlogn)。

4,空间复杂度:O(logn)。

public static void quickSort(int[] nums,int low ,int high){//快速排序

        if(low<high) {          
                int dp=partition(nums,low,high);
                quickSort(nums,low,dp-1);
                quickSort(nums,dp+1,high);                          

        }else{
            return;
        }       

    }
    public static int partition(int[] nums,int low ,int high){

        int pivot=nums[low];
        while(low<high){

            while(low < high && nums[high]>=pivot)
                high--;         
            nums[low]=nums[high];


            while(low < high && nums[low]<=pivot)
                low++;

            nums[high]=nums[low];

        }
        nums[low]=pivot;//此时low等于high,所以,也可以写成nums[high]=pivot;

        return low; //此时low等于high,所以返回任意一个都是正确的 
    }

示例数组:{12,5,9,20,6,31,24} 结果:

5.简单选择排序

1,定义:第i趟通过n-i次关键码的比较,在n-i-1(1<=i<=n-1)个记录中选取关键码最小的记录,并和第i个记录交换作为有序序列的第i个记录。

2,时间复杂度:最好,最坏,平均的时间复杂度都是O(n^2)。

3,空间复杂度:O(1)。

        public static void selectSort(int[] nums){//简单选择排序
        for(int i=0;i<nums.length-1;i++){
            int sIndex=i;//最小数下标
            int sNum=nums[i];//最小数大小        
            for(int j=i+1;j<nums.length;j++){
                if(nums[j]<sNum){
                    sIndex=j;
                    sNum=nums[j];
                }

            }
            //交换
            int temp=nums[i];
            nums[i]=nums[sIndex];
            nums[sIndex]=temp;

            System.out.print(i+1+":");
            for(int a:nums) 
                System.out.print(a+" ");
            System.out.println();

        }
    }

示例数组:{12,5,9,20,6,31,24} 结果:

6.堆排序

1,堆排序是对简单选择排序的改进。

2,首先将待排序的记录序列构造成一个堆,此时,选出了堆中所有记录的最大者即堆顶记录,然后将他从堆中移走,并将剩下的记录再调整成堆,这样又找出了次大的记录,以此类推,直到堆中只有一个记录为止。

3,时间复杂度:最好,最坏,平均的时间复杂度都是O(nlogn)。

4,空间复杂度:O(nlogn)。

public static void heapSort(int[] nums) {//堆排序
    if (nums == null || nums.length <= 1) {
         return;
    }

    buildMaxHeap(nums);//调用建立堆的函数

    //将堆顶元素调整至数组最后,然后,将当前堆继续调整为大顶堆
    for (int i = nums.length - 1; i >= 1; i--) {

        int temp=nums[0];
        nums[0]=nums[i];
        nums[i]=temp;

        maxHeap(nums, i, 0);


        System.out.print(nums.length-i+":");
        for(int a:nums) 
        System.out.print(a+" ");
        System.out.println();
    }
}

private static void buildMaxHeap(int[] nums) {//建立堆
    if (nums == null || nums.length <= 1) {
        return;
    }

    int half = nums.length / 2;
    for (int i = half; i >= 0; i--) {
        maxHeap(nums, nums.length, i);
    }
}

private static void maxHeap(int[] nums, int heapSize, int index) {//递归调整为大顶堆

    int left = index * 2 + 1;
    int right = index * 2 + 2;

    if( left > heapSize && right > heapSize ){
           //没有这个return,也是正确的,好吧!我没有看懂~
           return;
    }

    int largest = index;
    if (left < heapSize && nums[left] > nums[index]) {
        largest = left;
    }

    if (right < heapSize && nums[right] >nums[largest]) {
        largest = right;
    }

    if (index != largest) {         
        int temp=nums[index];
        nums[index]=nums[largest];
        nums[largest]=temp;

        maxHeap(nums, heapSize, largest);
    }


}

示例数组:{12,5,9,20,6,31,24} 结果:代码参考链接

7.二路归并排序

1,定义:将若干个有序序列进行两两归并,直至所有待排记录都在一个有序序列为止。

2,时间复杂度:最好,最坏,平均都是O(nlogn)。

3,空间复杂度:O(n)。

 public static void mergeSort(int[] a, int left, int right) {

       if(left<right){

           //int center = (left + right) >> 1;
           int center=(left+right)/2;
           mergeSort(a, left, center);
           mergeSort(a, center + 1, right);
           merge(a, left, center, right);
        }else{

            return;
        }
}

    public static void merge(int[] data, int left, int center, int right) {
        int[] tmpArr = new int[right+1];
        int mid = center + 1;
        int index = left; // index记录临时数组的索引
        int tmp = left;

        // 从两个数组中取出最小的放入中临时数组
        while (left <= center && mid <= right) {
            tmpArr[index++] = (data[left] <= data[mid]) ? data[left++]: data[mid++];
        }
        // 剩余部分依次放入临时数组
        while (mid <= right) {
            tmpArr[index++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[index++] = data[left++];
        }
        // 将临时数组中的内容复制回原数组
        for (int i = tmp; i <= right; i++) {
            data[i] = tmpArr[i];
        }
        System.out.println(Arrays.toString(data));
 }

    public static void main(String[] args) {
        int[] arr={12,5,9,20,6,31,24};
        mergeSort(arr, 0, arr.length-1);
    }

示例数组:{12,5,9,20,6,31,24} 结果:

 





收藏 推荐 打印 | 录入:elainebo | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款