纵有疾风起
人生不言弃

排序算法java实现

1. 插入排序

  原理:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止。
    算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是
    1 + 2 + 3 + …… + N = O(N ^ 2)的复杂度。

// 插入排序void InsertSort(int array[], int length){    int i, j, key;    for (i = 1; i < length; i++)    {        key = array;        // 把i之前大于array的数据向后移动        for (j = i - 1; j >= 0 && array[j] > key; j--)        {            array[j + 1] = array[j];        }        // 在合适位置安放当前元素        array[j + 1] = key;    }}

2.shell排序  

原理:将序列分成子序列,然后分别对子序列进行排序,最后将子序列组合起来。每次排序把序列的元素按照某个增量分成几个子序列对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了。

// shell排序void ShellSort(int array[], int length){    int temp;    // 增量从数组长度的一半开始,每次减小一倍    for (int increment = length / 2; increment > 0;increment /= 2)        for (int i = increment; i < length; ++i)        {            temp = array;            // 对一组增量为increment的元素进行插入排序            for (int j = i; j >= increment; j -= increment)            {                // 把i之前大于array的数据向后移动                if (temp < array[j - increment])                {                    array[j] = array[j - increment];                }                else                {                    break;                }            }            // 在合适位置安放当前元素            array[j] = temp;        }}

3.冒泡排序 

原理:每次遍历完序列都把最大(小)的元素放在最前面,然后再对剩下的序列重复前面的一个过程,每次遍历完之后待排序序列就少一个元素,当待排序序列减小为只有一个元素的时候排序就结束了。因此,复杂度在最坏的情况下是O(N ^ 2) 冒泡排序是稳定的,不会改变相同元素的相对顺序

void  Swap( int   * a,  int   * b)  {     int  temp;    temp  =   * a;    * a    =   * b;    * b    =  temp;}  //  冒泡排序 void  BubbleSort( int  array[],  int  length)  {     //  记录一次遍历中是否有元素的交换,总是与相邻的元素比较,并向前移    bool  exchange;     for  ( int  i = 0 ; i<length;++ i)      {        exchange= false ;         for  ( int j=i+1 ; j< length;++j)          {             if  (array[j] < array)              {                exchange= true ;                Swap( & array[j],  & array);            }        }         //  如果这次遍历没有元素的交换,那么排序结束          if  ( false   ==  exchange)             break ;    }}

4.快速排序 

原理:选定一个枢纽元素,对待排序序列进行分割,分割之后的序列一个部分小于枢纽元素,一个部分大于枢纽元素,再对这两个分割好的子序列进行上述的过程。 

  假设输入的数组中有k个小于轴值的结点,于是这些结点被放到数组最左边的k个位置上,而大于轴值得被放到数组最右边的n-k个位置上。

// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素int Partition(int array[], int low, int high){    // 采用子序列的第一个元素为枢纽元素    int pivot = array[low];    while (low < high)    {        // 从后往前在后半部分中寻找第一个小于枢纽元素的元素        while (low < high && array[high] >= pivot)        {            --high;        }        // 将这个比枢纽元素小的元素交换到前半部分        Swap(&array[low], &array[high]);        // 从前往后在前半部分中寻找第一个大于枢纽元素的元素        while (low < high && array[low] <= pivot)        {            ++low;        }        // 将这个比枢纽元素大的元素交换到后半部分        Swap(&array[low], &array[high]);    }    // 返回枢纽元素所在的位置    return low;}// 快速排序void QuickSort(int array[], int low, int high){    if (low < high)    {        int n = Partition(array, low, high);        QuickSort(array, low, n);        QuickSort(array, n + 1, high);    }}

 5. 归并排序

 原理:把待排序序列分成相同大小的两个部分,依次对这两部分进行归并排序,完毕之后再按照顺序进行合并

 两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.归并排序的一种稳定排序,即相等元素的顺序不会改变.时间复杂度为O(nlogn),空间复杂度为log(n)

// 归并排序中的合并算法void Merge(int array[], int start, int mid, int end){    int temp1[10], temp2[10];    int n1, n2;    n1 = mid - start + 1;    n2 = end - mid;    // 拷贝前半部分数组    for (int i = 0; i < n1; i++)    {        temp1 = array[start + i];    }    // 拷贝后半部分数组    for (int i = 0; i < n2; i++)    {        temp2 = array[mid + i + 1];    }    // 把后面的元素设置的很大    temp1[n1] = temp2[n2] = 1000;    // 逐个扫描两部分数组然后放到相应的位置去    for (int k = start, i = 0, j = 0; k <= end; k++)    {        if (temp1 <= temp2[j])        {            array[k] = temp1;            i++;        }        else        {            array[k] = temp2[j];            j++;        }    }}// 归并排序void MergeSort(int array[], int start, int end){    if (start < end)    {        int i;        i = (end + start) / 2;        // 对前半部分进行排序        MergeSort(array, start, i);        // 对后半部分进行排序        MergeSort(array, i + 1, end);        // 合并前后两部分        Merge(array, start, i, end);    }}

 6.选择排序

原理 : 每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

  第i次是选择数组中第i小的记录,并将该记录放到数组的第i个位置。

package sort.select;import java.util.Random;/**  * @author liangge *  */public class Main {public static void main(String[] args) {Random ran = new Random();int[] sort = new int[10];for (int i = 0; i < 10; i++) {sort[i] = ran.nextInt(50);}System.out.print("排序前的数组为");for (int i : sort) {System.out.print(i + " ");}selectSort(sort);System.out.println();System.out.print("排序后的数组为");for (int i : sort) {System.out.print(i + " ");}}/** * 选择排序 * @param sort */private static void selectSort(int[] sort){for(int i =0;i<sort.length-1;i++){for(int j = i+1;j<sort.length;j++){if(sort[j]<sort[i]){int temp = sort[j];sort[j] = sort[i];sort[i] = temp;}}}}}

7.堆排序

堆的定义:

n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):

(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)

  满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的

若将此序列所存储的向量R[1……n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素。

排序算法java实现插图

堆排序算法的过程如下:1)得到当前序列的最小(大)的元素 2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面 3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质。重复上面的过程,直到序列调整完毕为止。

// array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度void HeapAdjust(int array[], int i, int nLength){    int nChild, nTemp;    for (nTemp = array; 2 * i + 1 < nLength; i = nChild)    {        // 子结点的位置是 父结点位置 * 2 + 1        nChild = 2 * i + 1;        // 得到子结点中较大的结点        if (nChild != nLength - 1 && array[nChild + 1] > array[nChild])            ++nChild;        // 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点        if (nTemp < array[nChild])        {            array = array[nChild];        }        else    // 否则退出循环        {            break;        }    }    // 最后把需要调整的元素值放到合适的位置    array = nTemp;}// 堆排序算法void HeapSort(int array[], int length){    // 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素    for (int i = length / 2 - 1; i >= 0; --i)    {        HeapAdjust(array, i, length);    }    // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素    for (int i = length - 1; i > 0; --i)    {        // 把第一个元素和当前的最后一个元素交换,        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的        Swap(&array[0], &array);        // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值        HeapAdjust(array, 0, i);    }}

时间复杂度: 

           平均情况 最好情况 最坏情况 

归并排序 O(nlogn) O(nlogn) O(nlogn) 

快速排序 O(nlogn) O(nlogn) O(n2) 

希尔排序 O(n1.5) O(n) O(n1.5) 

插入排序 O(n2) O(n) O(n2) 

选择排序 O(n2) O(n2) O(n2) 

堆排序:时间复杂度O(nlogn) 
选择排序:时间复杂度O(n2) 
冒泡排序:时间复杂度O(n2) 

文章转载于:https://www.cnblogs.com/kxdblog/p/4324099.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 排序算法java实现

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活