黑马程序员技术交流社区

标题: 三种简单的排序 [打印本页]

---

作者: 小米锅巴    时间: 2018-8-28 23:06
标题: 三种简单的排序


    数组学完了可以进行一些排序的练习，在这里介绍最近学习的三种简单的排序方法。    首先是最常见，冒泡排序，第一次比较倒数第一个与倒数第二个比较，较小的换到倒数第二的位置，第二次倒数第二个与倒数第三个比较，较小的向上换，以此类推，第一轮共比较n-1，共比较n-1轮。同时还有一个减少比较次数的小技巧，设置一个boolean型的变量，当某一轮比较直到结束都没发生交换时，变量值设为false，从而结束循环，虽然增加了比较次数，但是减少了后续的比较，综合来说还是提升了性能。代码如下：
public static void optimizingBubble(int[] arr)
{   Boolean flag=true;
    for (int i = 0; i < arr.length&&flag; i++)
    {   flag=false;
        for (int j = arr.length-2; j >=i; j--)
        {   if(arr[j]>arr[j+1])
        {
            arr[j]=arr[j]+arr[j+1];
            arr[j+1]=arr[j]-arr[j+1];
            arr[j]=arr[j]-arr[j+1];
            flag=true;
        }

        }
    }
}  第二个排序是简单选择排序：基本思想为，从第一个值开始，向后比较找到最小的与第一的位置交换，然后从第二个开始向后比较，依此类推,代码如下：public static void selectionSort(int[] arr)
{
    for (int i = 0; i < arr.length; i++)
    {         int min=i;
        for (int j = i; j < arr.length; j++)
        {
            if(arr[min]>arr[j])
            {
                min=j;

            }
        }
        if(min!=i)
        {
            arr=arr+arr[min];
            arr[min]=arr-arr[min];
            arr=arr-arr[min];
        }
    }
}   
第三个排序是简单选择排序，这个排序性能要优于前两种排序，好像Java提供的某种排序方法中用的就是这种排序。基本思想为要排序的位置之前的序列为有序序列，若当前位置中存储的值小于前面的值，则进入循环查找适合自己的位置插入（即前面的数小于自己，后面的数大于自己），依此类推直到数组末尾。这里还有一点要提一下，书中给的数组0位没有值用来做哨兵，但正常情况下数组不会把0位置留出，所以我增加了一个复制数组，将数组长度加一留出0位用作哨兵的过程，此过程不在原排序算法中。代码如下：
public static int[] straightinsertsort(int[] arr)
{
    int[] arr1=new int[arr.length+1];
    for (int i = 1; i < arr1.length; i++)
    {
            arr1=arr[i-1];
    }
    for (int i = 1; i < arr1.length; i++)
    {
        if(arr1[i-1]>arr1)
        {
            arr1[0]=arr1;
            int j;
            for (j=i-1;arr1[j]>arr1[0]; j--)
            {
                arr1[j+1]=arr1[j];
            }
            arr1[j+1]=arr1[0];
        }

    }
    arr1[0]=0;
    return arr1;
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2