频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构与算法之排序(归纳总结二)
2014-12-24 09:09:22           
收藏   我要投稿
交换类排序主要是通过两两比较待排元素的关键字,若发现与排序要求相逆,则“交换”之。在这类排序方法中最常见的是起泡排序和快速排序,其中快速排序是一种在实际应用中具有很好表现的算法。

 

1.冒泡排序

 

a.算法描述

 

  起泡排序的思想非常简单。首先,将n个元素中的第一个和第二个进行比较,如果两个元素的位置为逆序,则交换两个元素的位置;进而比较第二个和第三个元素关键字,如此类推,直到比较第n-1个元素和第n个元素为止;上述过程描述了起泡排序的第一趟排序过程,在第一趟排序过程中,我们将关键字最大的元素通过交换操作放到了具有n个元素的序列的最一个位置上。然后进行第二趟排序,在第二趟排序过程中对元素序列的前n-1个元素进行相同操作,其结果是将关键字次大的元素通过交换放到第n-1个位置上。一般来说,第i趟排序是对元素序列的前n-i+1个元素进行排序,使得前n-i+1个元素中关键字最大的元素被放置到第n-i+1个位置上。排序共进行n-1趟,即可使得元素序列按关键字有序。

 

 

 

b.算法实现

 

 

public void bubbleSort(int[] r, int low, int high) {

    int n = high - low + 1;

    for (int i = 1; i < n; i++)

        for (int j = low; j <= high - i; j++)

            if (!compare(r[j], r[j + 1])) {

                int temp = r[j];

                r[j] = r[j + 1];

                r[j + 1] = temp;

            }

 

}

  

 

【效率分析】

空间效率:仅使用一个辅存单元。

时间效率:假设待排序的元素个数为n,则总共要进行n-1趟排序,对j 个元素的子序列进行一趟起泡排序需要进行j-1 次关键字比较,起泡排序的时间复杂度为Ο(n²)。

 

c.算法示例

 

BubbleSort.java

 

 

package com.test.sort.exchange;

 

 

public class BubbleSort {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

 

        System.out.println("冒泡排序排序功能实现》》》》");

        int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

 

        BubbleSort sort = new BubbleSort();

        System.out.println("排序之前序列:");

        sort.printArr(arr);

        sort.bubbleSort(arr, 0, arr.length - 1);

        System.out.println("排序之后序列:");;

        sort.printArr(arr);

    }

 

    public void bubbleSort(int[] r, int low, int high) {

        int n = high - low + 1;

        for (int i = 1; i < n; i++)

            for (int j = low; j <= high - i; j++)

                if (!compare(r[j], r[j + 1])) {

                    int temp = r[j];

                    r[j] = r[j + 1];

                    r[j + 1] = temp;

                }

 

    }// end of bubbleSort

 

    public boolean compare(int paramA, int paramB) {

        if (paramA < paramB) {

            return true;

        } else {

            return false;

        }

    }

 

    /**

     * 依次打印出数组元素

     */

    public void printArr(int[] arr) {

        if (arr != null) {

            for (int temp : arr) {

                System.out.print(temp + "   ");

            }

            System.out.println();

        }

    }

 

}

  

 

d.结果输出

 

 

 

2.快速排序

 

a.算法描述

 

  快速排序是将分治法运用到排序问题中的一个典型例子,快速排序的基本思想是:通过一个枢轴(pivot)元素将n个元素的序列分为左、右两个子序列Ll和Lr,其中子序列Ll中的元素均比枢轴元素小,而子序列Lr中的元素均比枢轴元素大,然后对左、右子序列分别进行快速排序,在将左、右子序列排好序后,则整个序列有序,而对左右子序列的排序过程直到子序列中只包含一个元素时结束,此时左、右子序列由于只包含一个元素则自然有序。用分治法的三个步骤来描述快速排序的过程如下:

 

  1. 划分步骤:通过枢轴元素x将序列一分为二, 且左子序列的元素均小于x,右子序列的元素均大于x;

  2. 治理步骤:递归的对左、右子序列排序;

  3. 组合步骤:无

  从上面快速排序算法的描述中我们看到,快速排序算法的实现依赖于按照枢轴元素x对待排序序列进行划分的过程。对待排序序列进行划分的做法是:使用两个指针low 和high分别指向待划分序列r的范围,取low所指元素为枢轴,即pivot = r[low]。划分首先从high所指位置的元素起向前逐一搜索到第一个比pivot小的元素,并将其设置到low所指的位置;然后从low所指位置的元素起向后逐一搜索到第一个比pivot大的元素,并将其设置到high所指的位置;不断重复上述两步直到low = high为止,最后将pivot设置到low与high共同指向的位置。使用上述划分方法即可将待排序序列按枢轴元素pivot分成两个子序列,当然pivot的选择不一定必须是r[low],而可以是r[low..high]之间的任何数据元素。

 

b.算法实现

 

 

//在划分算法的基础上,快速排序算法的递归实现   

 public void quickSort(int[] r, int low, int high) {

        if (low < high) {

            int pa = partition(r, low, high);

            quickSort(r, low, pa - 1);

            quickSort(r, pa + 1, high);

        }

    }

  //将序列划分为两个子序列并返回枢轴元素的位置

    private int partition(int[] r, int low, int high) {

        int pivot = r[low]; // 使用r[low]作为枢轴元素

        while (low < high) { // 从两端交替向内扫描

            while (low < high && !compare(r[high], pivot))

                high--;

            r[low] = r[high]; // 将比pivot小的元素移向低端

            while (low < high && compare(r[low], pivot))

                low++;

            r[high] = r[low]; // 将比pivot大的元素移向高端

 

        }

        r[low] = pivot; // 设置枢轴

        return low; // 返回枢轴元素位置

    }

 

【效率分析】

空间效率:不确定,最坏情况下是n。

时间效率:假设待排序的元素个数为n,则总共要进行n-1趟排序,对j 个元素的子序列进行一趟起泡排序需要进行j-1 次关键字比较,起泡排序的时间复杂度为Ο(n log n)。

 

c.算法示例

 

QuickSort.java

 

 

package com.test.sort.exchange;

 

public class QuickSort {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

 

        System.out.println("快速排序排序功能实现》》》》");

        int[] arr = { 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 };

 

        QuickSort sort = new QuickSort();

        System.out.println("排序之前序列:");

        sort.printArr(arr);

        sort.quickSort(arr, 0, arr.length - 1);

        System.out.println("排序之后序列:");;

        sort.printArr(arr);

    }

 

    public void quickSort(int[] r, int low, int high) {

        if (low < high) {

            int pa = partition(r, low, high);

            quickSort(r, low, pa - 1);

            quickSort(r, pa + 1, high);

        }

    }

 

    private int partition(int[] r, int low, int high) {

        int pivot = r[low]; // 使用r[low]作为枢轴元素

        while (low < high) { // 从两端交替向内扫描

            while (low < high && !compare(r[high], pivot))

                high--;

            r[low] = r[high]; // 将比pivot小的元素移向低端

            while (low < high && compare(r[low], pivot))

                low++;

            r[high] = r[low]; // 将比pivot大的元素移向高端

 

        }

        r[low] = pivot; // 设置枢轴

        return low; // 返回枢轴元素位置

    }

 

    public boolean compare(int paramA, int paramB) {

        if (paramA < paramB) {

            return true;

        } else {

            return false;

        }

    }

 

    /**

     * 依次打印出数组元素

     */

    public void printArr(int[] arr) {

        if (arr != null) {

            for (int temp : arr) {

                System.out.print(temp + "   ");

            }

            System.out.println();

        }

    }

}

点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 算法
上一篇:[布局] bootstrap基本标签总结
下一篇:在 Swift 中实现单例方法
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站