精华内容
下载资源
问答
  • 交换类排序:主要是不断的比较两个元素的大小并交换其原始的位置,完成一趟排序之后,最大的元素(或最小的元素)被排在最后(或者最前)。重复以上操作若干趟后,元素序列成为一个有序序列。主要有冒泡排序和快速排序。...

    交换类排序:主要是不断的比较两个元素的大小并交换其原始的位置,完成一趟排序之后,最大的元素(或最小的元素)被排在最后(或者最前)。重复以上操作若干趟后,元素序列成为一个有序序列。主要有冒泡排序快速排序。时间复杂度分别为:O(n^2)O(nlogn)

    冒泡排序思想依次比较两个相邻的数,把较小的数放在前面,把较大的数放在后面。

    快速排序的思想:快排不是比较两个相邻的元素,而是将指定的元素与序列中的元素依次比较,将逆序的两个元素交换

    下面是简单的冒泡排序和快排的简单操作:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    /***********************************************************/
    // 程序名称:SwapSort.cpp
    // 程序目的:内部排序法---交换式排序
    // 程序来源:数据结构与算法分析(C语言版) P-237
    // 日期:2013-9-4 15:20:37 JohnnyHu修改
    /***********************************************************/

    #include <stdio.h>
    #include <stdlib.h>

    #define Error( str )        FatalError( str )
    #define FatalError( str )   fprintf( stderr, "%s\n", str ), exit( 1 )

    #define  MAX    5   
    typedef int ElementType;

    void Swap(ElementType& lValue, ElementType& rValue)
    {
        ElementType tmp = lValue;
        lValue = tmp;
        lValue = rValue;
        rValue = tmp;
    }

    void BubbleSort(ElementType a[], int n);
    void InsertionSort(ElementType a[], int n);
    void QuickSort1(ElementType a[], int n);
    void PrintSort(ElementType a[], int n);

    int main(void)
    {
        int data[MAX] = {891245833};

        printf("排序前: ");
        PrintSort(data, MAX);

        //BubbleSort(data, MAX);
        QuickSort1(data, MAX);
        //QuickSort2(data, MAX);

        printf("排序后: ");
        PrintSort(data, MAX);

        return 0;
    }

    /************************************************************************/
    // 冒泡排序
    /************************************************************************/

    void BubbleSort(ElementType a[], int n)
    {
        bool bChanged;      // 记录数值位置是否交换
        bChanged = true;
        for (int i = n-1; i > 1 && bChanged; i--)
        {
            bChanged = false;
            for (int j=0; j < i; j++)
            {
                if (a[j] > a[j+1])
                {
                    Swap(a[j], a[j+1]); // 较大的数据始终在后面
                    bChanged = true;
                }
            }
        }

        return;
    }

    /************************************************************************/
    // 直接插入插入排序
    /************************************************************************/

    void InsertionSort(ElementType a[], int n)
    {
        ElementType tmp;
        for (int i = 1; i < n; i++)
        {
            tmp = a[i];     // 取出第i个元素

            int j = i;
            for ( ; j > 0 && a[j-1] > tmp; j--) 
            { // 从后往前寻找插入位置
                a[j] = a[j - 1];
            }
            a[j] = tmp;     // a[i]插入正确位置
        }
    }

    // 快排的核心部分
    void Qsort1(ElementType a[], int low, int high)
    {
        int left = low; 
        int right = high;
        ElementType pivot = a[low]; // 轴枢元素
        while (left < right)
        {
            while (left < right && pivot <= a[right])
                right--;        // 从后往前找小于pivot的元素
            if (left < right)
            {   // 将小于pivot的元素a[right]存入a[left]
                a[left] = a[right];
                left++;
            }

            while (left < right && pivot > a[left])
                left++;     // 从前往后找大于pivot的元素
            if (left < right)
            {
                a[right] = a[left];
                right--;
            }
        }
        a[left] = pivot;    // 轴枢元素存入a[left]

        if (low < left)
            Qsort1(a, low, left - 1);
        if (left > high)
            Qsort1(a, right+1, high);

        return;
    }
    /************************************************************************/
    // 快速排序1
    /************************************************************************/

    void QuickSort1(ElementType a[], int n)
    {
        int low, high;

        low = 0;
        high = n - 1;
        Qsort1(a, low, high);

        return;
    }

    /************************************************************************/
    // 打印排序表
    /************************************************************************/

    void PrintSort(ElementType a[], int n)
    {
        for (int i = 0; i < n; i++)
            printf("[%d]\t", a[i]);
        printf("\n");

        return;
    }
    输出结果:



    当然冒泡排序也可以这样写:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /************************************************************************/
    // 冒泡排序
    /************************************************************************/

    void BubbleSort(ElementType a[], int n)
    {
        //bool bChanged;        // 记录数值位置是否交换
        //bChanged = true;
        //for (int i = n-1; i > 1 && bChanged; i--)
        //{
        //  bChanged = false;
        //  for (int j=0; j < i; j++)
        //  {
        //      if (a[j] > a[j+1])
        //      {
        //          Swap(a[j], a[j+1]); // 较大的数据始终在后面
        //          bChanged = true;
        //      }
        //  }
        //}

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n - i - 1; i++)
            {
                if (a[j] > a[j=1])
                    Swap(a[j], a[j+1]);
            }
        }

        return;
    }
    很简单的一个二重循环,但就效率来见,肯定不如上面的经典下面,但二重循环更易理解。


    上面的快排1是每次排序时均将第一个元素作为轴枢元素,是最为简洁的一种,其实,轴枢元素的选择有多种方法,轴枢元素的选择对快排算法的效率有着重大的影响,所以上面的快排1有一定的缺陷,下面介绍快排2,改变主意针对的是轴枢元素的选择采用三数值分割策略:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    /************************************************************************/
    // 直接插入插入排序
    /************************************************************************/

    void InsertionSort(ElementType a[], int n)
    {
        ElementType tmp;
        for (int i = 1; i < n; i++)
        {
            tmp = a[i];     // 取出第i个元素

            int j = i;
            for ( ; j > 0 && a[j-1] > tmp; j--) 
            { // 从后往前寻找插入位置
                a[j] = a[j - 1];
            }
            a[j] = tmp;     // a[i]插入正确位置
        }
    }

    // 3数中值分割法
    ElementType Median3(ElementType a[], int letf, int right)
    {
        int center = (letf + right) / 2;

        if (a[letf] > a[center])
            Swap(a[letf], a[center]);
        if (a[letf] > a[right])
            Swap(a[letf], a[right]);
        if (a[center] > a[right])
            Swap(a[center], a[right]);
        // 此时a[left] <= a[center] <= a[right]

        Swap(a[center], a[right - 1]);  // 将枢纽元放到数组right-1的位置

        return a[right - 1];        // 放回枢纽元
            
    }
     
    // 快排核心部分
    #define  CUTOFF     3
    void Qsort2(ElementType a[], int left, int right)
    {
        ElementType pivot;      // 枢纽元

        if (left + CUTOFF <= right) 
        { // 保证数组中有3个以上的元素
            pivot = Median3(a, left, right);
            int i = left;
            int j = right - 1;

            for ( ; ; )
            {
                while (a[++i] < pivot) { }
                while (a[--j] > pivot) { }
                if (i < j)
                    Swap(a[i], a[j]);
                else 
                    break;
            }
            Swap(a[i], a[right - 1]);   // 将pivot在存储在right-1中

            Qsort2(a, left, i - 1);
            Qsort2(a, i + 1, right);
        }
        else    // 在子数组上j进行插入排序
            InsertionSort(a + left, right - left + 1);

        return;
    }

    /************************************************************************/
    // 快速排序2
    /************************************************************************/

    void QuickSort2(ElementType a[], int n)
    {
        Qsort2(a, 0, n - 1);
    }
    相对于快排1,快排2在平均处理数据的速度上,占有一定优势。


    展开全文
  • 散列排序法

    千次阅读 2012-12-14 11:34:46
    排序法总体上可以分两大,一是基于‘比较’的,主要有大家非常熟悉的:选择排序,交换排序,插入排序,归并排序等,其算法的复杂度也是用‘比较’的次数衡量的,其中有非常高效和优秀的‘快速排序’,可以说是...

    原来写过一篇文章在笔记本里,后来中病毒我把它格了,也没上网没机会发表出来,主要内容是关于一种比较另类的排序方法的,我叫它散列排序法。凭我的记忆把算法的主要思想写下来。

    排序法总体上可以分两大类,一类是基于‘比较’的,主要有大家非常熟悉的:选择排序,交换排序,插入排序,归并排序等,其算法的复杂度也是用‘比较’的次数衡量的,其中有非常高效和优秀的‘快速排序’,可以说是他们中间的佼佼者,无论从时间还是空间上说都有很好的性能;另外一类也就自然是不基于‘比较’的,《数据结构》上介绍过一种叫‘基数排序’,我觉得也很经典,今天我要向大家介绍的跟基数排序很类似,原理也非常简单。

    和基数排序的方法非常类似,也是采用分配和收集,而我管它叫‘散列’,因为就和hash散列表一样,而且我可以说当数据比较均匀的离散分布的时候,效率是非常高的,可以花很少的几次散列就得到有序结果。

    [写在前面,也跟基数排序一样只适用于整数排序,因为不基于比较就只能从元素,即数的本身出发了。]


    先举个例子,设待排序的数是:
    4,2,5,1,3

    我们排序的任务就是让上面一列数有序,看看我们要做的结果是什么:
    1,2,3,4,5

    于是我们的任务就是,把前面一列数各位数放到‘正确’的位置上去,使得它有序。而一个数和它的正确位置就是一个映射关系,于是我们就是要找到一个函数f(x),使f(x)->‘x的正确位置’!

    上面的例子非常简单,f(x)=x,但实际情况非常复杂,其实像这样的f(x)是不可能有很好的数学表达式的,别指望在这里做更多的努力。于是我着手找近似的f(x),我的想法是,只要让它不会错太多就行了,不完善的可以慢慢做得完善。

    实际上f(x)就是一个散列函数,只不过它不是用来检索而是用来排序,我给出一个f(x)=[(x-min)*(n-1)/(max-min)],其中min是这列数的最小值,max是这列数的最大值,n是这列数的个数,那值域就会在[0,n-1],再用这些值找散列存储位置。

    在这样一个近似的f(x)函数下,会出些‘意外’的情况,首先可能会有两个元素得到相同的f(x)值,也就是‘冲突’,冲突如何解决?可以采用拉链法,类似于hash表的冲突处理。

    为什么要用拉链法,其实可以从集合的角度看这个算法,实际上我是把整个数列看成一个集合,然后我着手把它分成更小一些的子集,同时使这些子集‘集合间有序’,所谓集合间有序是指:
    如果 集合A<集合B
    那么 对于任意的x,x属于A,又对于任意的y,y属于B,都成立x<y

    然后不断往下分,直到被分的集合中只含有一个元素为止,排序工作就完成了。

    再来个例子:
    1,4,3,7,3,2
    于是
    min=1,max=7,n=6
    f(x)=[(x-1)*5/6]
    第一次划分的结果是:
    收集链表ID:0 1 2 3 4 5
    [元素]      1 3 4     7
                2 3
    就得到了四个子集,设对应ID的子集记为[ID],那么它们是
    {[0],[1],[2],[5]}   (它们也是第一次划分f(x)的值域)
    它们是‘集合间有序’的。

    算法到此全部描述完了,另外我还想说点具体实现的过程,虽然没源代码了,还有些细节问题。

    1、f中的min,max该如何求?
    给我们的排序任务,只给出数据地址和数据元素,并没有给出min和max,是不是需要先求一下呢?如果要求一下,又回到了比较的方法,于是整个算法就不是很好的不基于比较的算法。我的看法是,具体排序的时候如果能给出来可以尽量给出(比如,按一个城市所有人的年龄排序,范围可以是0~150),如果真给不出来,没关系,我们取那种类型的数据的最小值和最大值。但是这不会影响到效率吗?后面再讨论效率。
    另外再提出个概念,叫‘区分度’,区分度就是指一次划分的时候,得到的子集内的元素的最大值和最小值之差的最大值;这样吧,可能不好理解。这样记,我记一次划分为:
    div(min,max):(这样记是因为,一次划分是跟min和max分不开的,确定了min和max才能划分)
    {parent} --> {[i]}
    那这次划分的区分度就是
    max{elem1-elem2|elem1,elem2属于[i]}
    在前面的例子中就是1,因为[0]中2-1最大。
    为什么要提这个概念,在你划分一次后如果没有得到结果,那必须再对子集进行划分,这时的子划分中的max-min正是前一次的区分度。如果还知道min,那子划分就确定了。而min是可以线性求出来的,于是子划分就完全确定下来了。
    区分度约为(max-min)/n *

    2、这个算法的效率如何?
    首先从时间上考虑。整个排序的过程可以看成是把一个有n个元素的集合分成n个只有一个元素的子集的过程。而就以划分的次数来衡量的话,最差的情况是,连续几次划分都没有分成功,原有集合本身做为子集,但是这样的情况不会持续很久,随着更加细致的划分,区分度会不断变小,区分度的迭代递推式是:d'=d/n,实际上是非常快速的收敛。其次,如果每一次划分只能分成两个子集,效率会如何呢?注意到划分出的子集是集合间有序的,这会联想到快速排序的一次划分,没错快速排序的一次划分能且只能将元素划分成两个部分,这两个部分有序,所以应该和快速排序的效率相当。最后,如果每一次划分能分成两个子集以上,效率会更高吗?不用我说了,应该会更高吧~~
    实际上对于离散分布比较均匀(等概率分布)的无序数,排起序来是非常高效的~!
    另外从空间上考虑。这就比快速排序差太多了,整个辅助空间需要得很大,基本上需要和原有数据量一样多的空间,应该是O(n),当n很大时,运行的实际耗时基本上都花在内存空间分配和回收上了。

    展开全文
  • 排序法大集合

    2015-10-26 18:27:33
    一.概念,分类  内排序的方法许多种,按所用策略不同,可归纳为五:插入排序、选择...交换排序主要包括气(冒)泡排序和快速排序。 二.主要排序方法 1.冒泡排序  已知一组无序数据a[1]、a[2]、……a

    一.概念,分类

                  内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序和分配排序。
             其中,插入排序主要包括直接插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括气(冒)泡排序和快速排序。

    二.主要排序方法

    1.冒泡排序
      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。
      优点:稳定;
      缺点:慢,每次只能移动相邻两个数据。

    2.选择排序
      冒泡排序的改进版。
      每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
      选择排序是不稳定的排序方法。
      n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
      ①初始状态:无序区为R[1..n],有序区为空。
      ②第1趟排序
      在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
      ……
      ③第i趟排序
      第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
      这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
      优点:移动数据的次数已知(n-1次);
      缺点:比较次数多。

    3.插入排序
      已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、b[2]、……b

    ,需将二者合并成一个升序数列。首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值,若b[1]仍然大于a[2],则继续跳过,直到b[1]小于a数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b

    用相同方法插入。(若无数组a,可将b[1]当作n=1的数组a)
      优点:稳定,快;
      缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。

    4.缩小增量排序
      由希尔在1959年提出,又称希尔排序(shell排序)。
      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入排序的效果很好。首先取一增量d(d<n),将a[1]、a[1+d]、a[1+2d]……列为第一组,a[2]、a[2+d]、a[2+2d]……列为第二组……,a[d]、a[2d]、a[3d]……列为最后一组以次类推,在各组内用插入排序,然后取d'<d,重复上述操作,直到d=1。
      优点:快,数据移动少;
      缺点:不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。

    5.快速排序
      快速排序是目前已知的最快的排序方法。
      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数据>a[x],然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
      优点:极快,数据移动少;
      缺点:不稳定。

    6.箱排序
      已知一组无序正整数数据a[1]、a[2]、……a[n],需将其按升序排列。首先定义一个数组x

    ,且m>=a[1]、a[2]、……a[n],接着循环n次,每次x[a]++.
      优点:快,效率达到O(1)
      缺点:数据范围必须为正整数并且比较小

    7.归并排序
      归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。 
      归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

    三.用C/C++语言描述上述算法

    1.冒泡法

    void bubble_sort(int a[], int n)

    {

        int i = n-1; bool change = true;

        for (; i>=1&&change; --i)

                  {

                       change = false;

                       for (int j = 0; j<i; ++j)

                                {

                                      if (a[j]>a[j+1])

                                          {

                                                 int nTemp = a[j+1];

                                                 a[j+1] = a[j];

                                                 a[j] = nTemp;

                                                 change = true;

                                            }

                                 }

        }
    }

    2.选择排序法

    #include<iostream>
    using namespace std;

    int main()
    {

         int num[10] = {9,8,10,3,4,6,4,7,2,1};
         cout<<"排序前:"<<endl; 
         for (int m = 0;m < 10;m++)
             {

                cout<<num

    <<" ";
             }
          for (int i = 0;i < 10;i++)

            {
                int pos = i;

                for (int j = i;j < 10;j++)

                     {
                          if (num[pos] > num[j])
                                   {

                                             pos = j;

                                    }

                     }
                 int tem;

                tem = num[pos];
                num[pos] = num[i];
                num[i] = tem;

            }
    cout<<endl<<"排序后:"<<endl; 
            for (int m = 0;m < 10;m++)
                {
                    cout<<num

    <<" ";
                }
    return 0;
    }

    3.插入排序法
    void InsertSort(char array[],unsigned int n)
    {
             int i,j;

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

                        temp = array;//store the original sorted array in temp
                                 for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
                                            {
                                                array[j]=array[j-1];//all larger elements are moved one pot to the right
                                             }
                          array[j]=temp;
                    }

    }
    4.缩小增量排序

    void ShellPass(SeqList R,int d)
    {//希尔排序中的一趟排序,d为当前增量
            for(i=d+1;i<=n;i++) //将R[d+1..n]分别插入各组当前的有序区

                  if(R[ i ].key<R[i-d].key)

                         {
                                  R[0]=R;j=i-d; //R[0]只是暂存单元,不是哨兵

                                              do

                                                     {//查找R的插入位置

                                                          R[j+d]=R[j]; //后移记录

                                                          j=j-d; //查找前一记录
                                                     }while(j>0&&R[0].key<R[j].key);
                                  R[j+d]=R[0]; //插入R到正确的位置上
                           } //endif

    } //ShellPass
    void ShellSort(SeqList R)

    {
                 int increment=n; //增量初值,不妨设n>0
                  do

                         {

                                increment=increment/3+1; //求下一增量
                               ShellPass(R,increment); //一趟增量为increment的Shell插入排序
                         }while(increment>1)
    } //ShellSort

    5.快速排序

    int partions(int a[],int low,int high)

    {
             int pivotkey=a[low];
             a[0]=a[low];
             while(low<high)
                   {
                         while(low<high && a[high]>=pivotkey)
                               --high;
                         a[low]=a[high];
                         while(low<high && a[low]<=pivotkey)
                                ++low;
                          a[high]=a[low];

                    }
              a[low]=a[0];
              return low;

    }
    void qsort(int a[],int low,int high)
    {
              int pivottag;
              if(low<high)
                   { //递归调用
                         pivottag=partions(a,low,high);
                         qsort(a,low,pivottag-1);    

                         qsort(a,pivottag+1,high);
                    }
    }
    void quicksort(int a[],int n)
    {
              qsort(a,1,n);
    }


     

    展开全文
  • Java中利用数组进行数字排序一般4种方法:选择排序法、冒泡法、快速排序法、插入排序法。选择排序是先将数组中的第一个数作为最大或最小数,然后...快速排序法主要是运用Arrays中的Arrays.sort方法()实现。插...

    Java中利用数组进行数字排序一般有4种方法:选择排序法、冒泡法、快速排序法、插入排序法。

    选择排序是先将数组中的第一个数作为最大或最小数,然后通过循环比较交换最大数或最小数与一轮比较中第一个数位置进行排序;

    冒泡排序也是先将数组中的第一个数作为最大或最小数,循环比较相邻两个数的大小,满足条件就互换位置,将最大数或最小数沉底;

    快速排序法主要是运用Arrays类中的Arrays.sort方法()实现。

    插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序。

    选择排序法

    packagecom.lovo;public classTest01 {public static voidmain(String[] args) {int[] a = new int[5];for(int i = 0; i < a.length; i++) {

    a[i]= (int) (Math.random() * 99 + 1);

    System.out.print(a[i]+ " ");

    }//简单选择排序

    for(int i = 0; i < a.length - 1; i++) {int minIndex =i;for(int j = i + 1; j < a.length; j++) {if(a[j]

    minIndex=j;

    }

    }if(minIndex !=i) {int temp =a[i];

    a[i]=a[minIndex];

    a[minIndex]=temp;

    }

    }for(intx : a) {

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

    }

    }

    }

    冒泡排序法

    package com.lovo;

    public class Test02 {

    public static void main(String[] args) {

    int[] a = new int[5];

    for(int i = 0; i < a.length; i++) {

    a[i] = (int) (Math.random() * 99 + 1);

    System.out.print(a[i] + " ");

    }

    // 冒泡排序

    boolean swapped = true;// 有没有发生过交换

    for(int i = 1; swapped && i <= a.length - 1; i++) {

    swapped = false;

    for(int j = 0; j < a.length - i; j++) {

    if(a[j] > a[j + 1]) {

    int temp = a[j];

    a[j] = a[j + 1];

    a[j + 1] = temp;

    swapped = true;

    }

    }

    }

    for(int x : a) {

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

    }

    }

    }

    快速排序法

    package com.lovo;

    import java.util.Arrays;

    public class Test03 {

    // 快速排序法

    public static void main(String[] args) {

    int[] a = new int[5];

    System.out.print("排序前: ");

    for (int i = 0; i < a.length; i++) {

    a[i] = (int) (Math.random() * 99 + 1);

    System.out.print(a[i] + " ");

    }

    System.out.print("\n排序后:");

    Arrays.sort(a); // 进行排序

    for (int x : a) {

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

    }

    }

    }

    展开全文
  • 常用排序算法总结

    2015-04-15 16:06:47
    生活中我们涉及到的排序算法主要有基本排序算法和多路归并排序算法。其中基本排序主要分配四大交换排序,选择排序,插入排序,合并排序。 其中交换排序分为:冒泡排序、快速排序;选择排序可分为:选择排序、堆...
  • 交换排序主要包括气(冒)泡排序和快速排序。  稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是...
  • java---数字排序

    2014-10-26 10:45:00
    Java中利用数组进行数字排序一般4种方法:选择排序法、冒泡法、快速排序法、插入排序法。 选择排序是先将数组中的第一个数作为最大或最小数,然后通过循环...快速排序法主要是运用Arrays中的Arrays.sort方法...
  • java Io流共涉及40多个,这些看上去很杂乱,但实际上很规则,而且彼此之间存在非常紧密的联系, Java Io流的40多个都是从如下4个抽象基类中派生出来的。 InputStream/Reader: 所有的输入流的基类,前者是...
  • C++程序员面试宝典

    热门讨论 2013-04-01 13:36:19
    面试题155 什么是快速排序 176 面试题156 什么是希尔(Shell)排序 177 面试题157 什么是堆排序 179 13.7 排序算法的总结 180 第14章 软件工程(教学视频:39分钟) 182 14.1 软件工程基础 182 面试题158 什么是软件...
  • 顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域,用指针来体现数据...
  • (8) 软件的调试方法主要有:强行排错、______和原因排除。 答:回溯 (9) 数据库系统的三级模式分别为______模式、内部级模式与外部级模式。 答:概念#概念级 (10) 数据字典是各类数据描述的集合,它通常包括...
  • 交换类排序法 B.插入类排序法 C.选择类排序法 D.建堆排序法 (43) 在深度为5的满二叉树中,叶子结点的个数为(C) A. 32 B. 31 C. 16 D. 15 (44) 对长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为(B) 注...
  • 常量与变量区别标识符关键字输入输出id求地址type求类型python变量是地址赋值可以改变类型python主要数据类型复数数据类型自适应变长整数intdel作用连续赋值交互对称赋值字符串转化与输入输出编程wmv多行拆分多行...
  • 排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、深度优先遍历,广度优先遍历,二叉搜索树等 图论:最短路径、最小生成树 动态规划:背包问题、最长子序列 数据结构,主要有如下几种: 数组与链表...
  • 3.1.3 快速排序的思想、时间复杂度、实现以及优化方法 3.1.4 IO模型——IO多路复用机制? 3.1.5 常用的Linux命令 3.1.6 C中变量的存储类型哪些? 3.1.7 动态规划的本质 3.1.8 实践中如何优化MySQL? 3.1.9 ...
  • 17、、法律的题目很少,主要集中在劳动和公司。偶是法学专业,劳动我印象里考了三道,一道是说周末加班后来又不补休的,用人单位须支付多少工资(150%、200%、300%、100%),一道是问哪个不算工伤(职业...
  • 实例104 使用Sort方法对数组进行快速排序 实例105 反转数组中元素的顺序 4.3 常用集合的使用 实例106 向班级集合中添加学生信息 实例107 使用哈希表对XML文件进行查询 实例108 计算两个矩形矩阵的乘积 第5章 ...
  • 实例104 使用Sort方法对数组进行快速排序 实例105 反转数组中元素的顺序 4.3 常用集合的使用 实例106 向班级集合中添加学生信息 实例107 使用哈希表对XML文件进行查询 实例108 计算两个矩形矩阵的乘积 第5章 ...
  • 实例104 使用Sort方法对数组进行快速排序 实例105 反转数组中元素的顺序 4.3 常用集合的使用 实例106 向班级集合中添加学生信息 实例107 使用哈希表对XML文件进行查询 实例108 计算两个矩形矩阵的乘积 第5章 ...
  • 主要内容C#开发环境的使用、C#语言基础应用、字符串处理技术、数组和集合的使用、面向对象编程技术、数据结构与算法、Windows窗体基础、特色窗体界面、窗体控制技术、MDI窗体和继承窗体、Windows常用控件的使用、...
  • 实例104 使用Sort方法对数组进行快速排序 124 实例105 反转数组中元素的顺序 125 4.3 常用集合的使用 126 实例106 向班级集合中添加学生信息 126 实例107 使用哈希表对XML文件进行查询 127 实例108 计算两个矩形矩阵...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    内容及步骤: 编写一个Complex,定义复数的加法、减法、乘法和除运算,要求在编写该时重载这些运算操作符,并重载I/O操作符,以便输入和输出复数; 实验报告要求: 按要求写出完整的实验代码; ...
  • 排序法哪些,其算法都是怎样的 如何将十进制字符串、十六进制字符串和二进制字符串互相转化 如何随机选号 第15章 发布程序 如何给软件加密和解密 如何使程序在开机时就自动运行 如何创建快捷方式 如何删除快捷...
  • 导师学习中,权值和阈值的调整只与网络输入关系,没有期望值,这算法大多用聚类,将输入模式归类于有限的类别。本章将详细分析两种 应用最广的导师学习神经网络(BP神经网络及RBF神经网络)的原理及其在...
  • C++ Standard Library:是一系列和函数的集合,使用核心语言编写,也是C++ISO自身标准的一部分。 Standard Template Library:标准模板库。 C POSIX library : POSIX系统的C标准库规范。 ISO C++ Standards ...
  • iPhone开发秘籍(第2版)--源代码

    热门讨论 2012-12-11 13:51:22
    CruiseYoung提供的带详细书签的电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 该资料是《iPhone开发秘籍:第2版》的源代码 对应的书籍资料见: iPhone开发秘籍:第2版(iphone开发必备佳作,在...
  • iPhone开发秘籍(第2版)--详细书签版

    热门讨论 2012-12-11 13:42:25
    CruiseYoung提供的带详细书签的电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 iPhone开发秘籍:第2版(iphone开发必备佳作,在第一版的基础上进行了全面修订和大量扩充) 基本信息 原书名: ...
  • 实例093 快速排序算法 实例094 归并排序算法 4.4 查找算法 实例095 顺序查找 实例096 二分法查找 实例097 分块查找 实例098 哈希查找 4.5 字符处理应用 实例099 简单的加密解密算法 实例100 字符串处理 ...

空空如也

空空如也

1 2
收藏数 37
精华内容 14
关键字:

交换类排序法主要有快速排序