java常见排序算法

梦里梦外; 2022-05-30 11:59 208阅读 0赞

#### java中常见的7种排序算法 ####

1.  冒泡（Bubble）排序——相邻交换
2.  选择排序——每次最小/大排在相应的位置
3.  插入排序——将下一个插入已排好的序列中
4.  壳（Shell）排序——缩小增量
5.  归并排序
6.  快速排序

### 1、冒泡（Bubble）排序 ###

void BubbleSortArray() 
    { 
          for(int i=1;i<n;i++) 
          { 
            for(int j=0;i<n-i;j++) 
             { 
                  if(a[j]>a[j+1])//比较交换相邻元素 
                   { 
                       int temp; 
                       temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; 
                   } 
             } 
          } 
    }

效率 O（n²）,适用于排序小列表。

### 2、选择排序 ###

void SelectSortArray() 
    { 
        int min_index; 
        for(int i=0;i<n-1;i++) 
        { 
             min_index=i; 
             for(int j=i+1;j<n;j++)//每次扫描选择最小项 
                if(arr[j]<arr[min_index])  min_index=j; 
             if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置 
             { 
                 int temp; 
                 temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp; 
            } 
        } 
    }

效率O（n²），适用于排序小的列表。

### 3、插入排序 ###

void InsertSortArray() 
    { 
            for(int i=1;i<n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分 
            { 
                int temp=arr[i];//temp标记为未排序第一个元素 
                int j=i-1; 
                while (j>=0 && arr[j]>temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/ 
                { 
                    arr[j+1]=arr[j]; 
                    j--; 
                } 
            arr[j+1]=temp; 
            } 
    }

最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表  
若列表基本有序，则插入排序比冒泡、选择更有效率。

### 4、壳（Shell）排序 ###

void ShellSortArray()
    {
        for ( int incr = 3; incr < 0; incr-- )                // 增量递减，以增量3，2，1为例 
        {
            for ( int L = 0; L < (n - 1) / incr; L++ )        // 重复分成的每个子列表 
            {
                for ( int i = L + incr; i < n; i += incr )     // 对每个子列表应用插入排序 
                {
                    int temp    = arr[i];
                    int j   = i - incr;
                    while ( j >= 0 && arr[j] > temp )
                    {
                        arr[j + incr]   = arr[j];
                        j -= incr;
                    }
                    arr[j + incr] = temp;
                }
            }
        }
    }

适用于排序小列表。  
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。  
壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。

### 5、归并排序 ###

void MergeSort(int low,int high) 
    {
        if(low>=high)   return;
        //每个子列表中剩下一个元素时停止 
        int mid=(low+high)/2;
        //将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表
        MergeSort(low,mid);
        //子列表进一步划分 
        MergeSort(mid+1,high);
        int [] B=new int [high-low+1];
        //新建一个数组，用于存放归并的元素 
        for (int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)
        /*两个子列表进行排序归并，直到两个子列表中的一个结束*/
        {
            if (arr[i]<=arr[j];
            ) 
                    {
                B[k]=arr[i];
                I++;
            } else
                        {
                B[k]=arr[j];
                j++;
            }
        }
        for (   ;j<=high;j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表 
        B[k]=arr[j];
        for (   ;i<=mid;i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中 
        B[k]=arr[i];
        for (int z=0;z<high-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中 
        arr[z]=B[z];
    }

效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。  
适用于排序大列表，基于分治法。

### 6、快速排序 ###

//a：待排序数组，low：最低位的下标，high：最高位的下标
    void quickSort(int a[],int low, int high)
    {
        if(low>=high)
        {
            return;
        }
        int left=low;
        int right=high;
        int key=a[left];    /*用数组的第一个记录作为分区元素*/
        while(left!=right){
            while(left<right&&a[right]>=key)    /*从右向左扫描，找第一个码值小于key的记录，并交换到key*/
                --right;
            a[left]=a[right];
            while(left<right&&a[left]<=key)
                ++left;
            a[right]=a[left];    /*从左向右扫描，找第一个码值大于key的记录，并交换到右边*/
        }
        a[left]=key;    /*分区元素放到正确位置*/
        quickSort(a,low,left-1);
        quickSort(a,left+1,high);
    }

平均效率O（nlogn），适用于排序大列表。  
最好的情况：是每趟排序结束后，每次划分使两个子文件的长度大致相等，时间复杂度为O（nlog2n）。  
最坏的情况：如果待排序列表已经排好序，第一趟经过n-1次比较后第一个记录保持位置不变，并得到一个n-1个元素的子记录；第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件，依次类推，时间O(n2)。