Java常用排序算法

    xiaoxiao2025-02-14  12

    1、冒泡排序

    冒泡排序是排序算法中最基本的一种排序方法,该方法逐次比较两个相邻数据的大小并交换位置来完成对数据排序,每次比较的结果都找出了这次比较中数据的最大项,因为是逐次比较,所以效率是O(N^2)的。

    [java]  view plain copy public void bubbleSort() {           int out,in;           for(out=index-1; out>1; --out) {               for(in=0; in<out; ++in) {                   if(array[in]>array[in+1]) {                       swap(in, in+1);                   }               }           }       }              public void swap(int dex1, int dex2) {           int temp = array[dex1];           array[dex1] = array[dex2];           array[dex2] = temp;       }  

    2、选择排序

    选择排序对冒泡排序进行了优化,在每次遍历比较的过程中不进行交换,而是记录本次遍历的最小值,在遍历结束后再将最小值移到这次遍历的开始位置。这样虽然比较次数没有改变,但交换的次数大大减少,一共只需要N次交换。因为比较的次数没变,所以效率任然是O(N^2)的。

    [java]  view plain copy public void selectionSort() {           int out, in;           for(out=0; out<index-1; ++out) {               int temp = out;               for(in=out+1; in<index; ++in) {                   if(array[in] < array[temp]) {                       temp = in;                   }               }               swap(out, temp);           }       }  

    3、插入排序

    插入排序充分利用已排列好的数据,然后将未排序的数据插入到已排数据的队伍当中,这样每插入一个未排序数据已排队伍都将增加一个成员,最终达到排序的目的。

    [java]  view plain copy public void insertionSort() {           int out ,in;           for(out=1; out<index; ++out) {               int temp = array[out];               in = out;               while(in>0 && temp<array[in-1]) {                   array[in] = array[in-1];                   --in;               }               array[in] = temp;           }       }  

    4、归并排序

    归并排序是将两个有序数组合并为一个有序数组的排序,应用在一般排序上要结合二分法递归地将数组依次归并,最终得到一个大的有序数组。归并的效率是O(NlogN)的,但要额外开辟一个数组来存放临时数据,所以占用空间要大一倍。

    [java]  view plain copy public void mergeSort() {           int[] newArray = new int[index];           recMergeSort(newArray, 0, index-1);                  }              private void recMergeSort(int[] data, int low, int upper) {           if(low == upper) {               return;           }           int mid = (low + upper)/2;           recMergeSort(data, mid+1, upper);           recMergeSort(data, low, mid);           merge(data, low, mid+1, upper);       }              private void merge(int[] data, int lowStart, int highStart, int upperBound) {           int j = 0;           int lowBound = lowStart;           int mid = highStart - 1;           int num = upperBound - lowStart + 1;                      while(lowStart<=mid && highStart<=upperBound) {               if(array[lowStart] < array[highStart]) {                   data[j++] = array[lowStart++];               } else {                   data[j++] = array[highStart++];               }           }                      while(lowStart<=mid) {               data[j++] = array[lowStart++];           }                      while(highStart<=upperBound) {               data[j++] = array[highStart++];           }                      for(j=0; j<num; j++) {               array[lowBound+j] = data[j];           }       }  

    5、希尔排序

    希尔排序是一种高级排序,它是由插入排序进化来的,插入排序是将未排的数据依次与前面已排好的数据进行比较移动,这样如果一个较小的数排在靠后的位置,那么要找到这个数的正确位置就要进行较多次移动。希尔排序改进了这种方式,它将每次比较的间隔扩大,排过一次之后数据就分阶段有序了,之后逐渐缩小这个间隔再进行排序。这样做的目的就是让数据一开始可以在一个较大的范围内进行移动,待基本有序后数据的移动量就小了很多。

    [java]  view plain copy public void shellSort() {           int in, out;           int h = 1;           int temp;           while(h < index/3) {               h = h*3+1;           }           while(h>0) {               for(out=h; out<index; ++out) {                   temp = array[out];                   in = out;                   while(in>h-1 && array[in-h] > temp) {                       array[in] = array[in-h];                       in -=h;                   }                   array[in] = temp;               }               h = (h-1)/3;           }       }  

     

    希尔排序中关键是对数据间隔h的选择,一个间隔序列是由Knuth提出的,即h=h*3+1,h的初始值为1,这是希尔排序中最优的间隔序列。

    6、快速排序

    快速排序是一种广泛使用的排序方法,效率可以达到O(NlogN),快速排序的原理是确定一个中间值pivot,将所有小于pivot的数据放在左侧,大于pivot的值放在右侧,之后再对左右两侧分别采取这种策略进行排序,直到这个过程结束。

    [java]  view plain copy private int partition(int left, int right, int pivot) {           int leftPtr = left;           int rightPtr = right-1;           while(true) {               while(array[++leftPtr] < pivot) ;               while(array[--rightPtr] > pivot);               if(leftPtr >= rightPtr) {                   break;               } else {                   swap(leftPtr, rightPtr);               }           }           swap(leftPtr, right-1);           return leftPtr;       }              private int median(int left, int right) {           int center = (left+right)/2;           if(array[left]>array[center]) {               swap(left, center);           }           if(array[left]>array[right]) {               swap(left, right);           }           if(array[center]>array[right]) {               swap(center, right);           }           swap(center, right-1);           return array[right-1];       }              private void manulSort(int left, int right) {           int size = right-left+1;           if(size <= 1return;           if(size == 2) {               if(array[left]>array[right]) swap(left, right);           } else {               if(array[left]>array[right-1]) swap(left, right-1);               if(array[left]>array[right]) swap(left, right);               if(array[right-1]>array[right]) swap(right-1, right);           }       }              private void recQuickSort(int left, int right) {           int size = right-left+1;           if(size<=3) {               manulSort(left, right);           } else {               int pivot = median(left, right);               int partition = partition(left, right, pivot);               recQuickSort(left, partition-1);               recQuickSort(partition+1, right);           }                  }              public void quickSort() {           recQuickSort(0, index-1);       }  

    快速排序的关键是确定中间值pivot,如果中间值选取的不好,会使快速排序的效率降到O(N^2)。上面的例子采用了三选一的策略来确定中间值,即在要排序的数据中选择左端、中间和右端三个数据后比较取中间值;还有在数据量较小时,比如小于三个则直接手动排序。

    快速排序选中间值实际上采用的是分治的思想,对数据的准确划分才能达到最高的效率,更深层的原理可以去看这篇文章

    转载请注明原文地址: https://ju.6miu.com/read-1296444.html
    最新回复(0)