当前位置： 首页 > news >正文

数据结构中的八大排序算法

news 来源：原创 2024/5/6 15:45:30

参考博文：http://blog.csdn.net/tan313/article/details/51146170

　　　　    http://blog.csdn.net/hguisu/article/details/7776068　   

一、冒泡排序

思想：重复走访过要排序的序列，一次比较两个元素，如果他们的顺序错误就将他们进行交换，一次冒上来的是最小的，其次是第二小。

时间复杂度：O(n^2)

空间复杂度:O(1)

稳定性：稳定

 1 /**
 2      * 冒泡排序
 3      * @param disOrderArray
 4      * @return
 5      */
 6     public static int[] BubbleSort(int[] disOrderArray) {
 7         int temp;
 8         // 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）
 9         for(int i=0;i<disOrderArray.length-1;i++)
10         {
11             // 把最小的数交换着"冒泡"的相对的最上边,一次冒上来的是最小的,其次是第二小的.
12             for(int j=disOrderArray.length-1;j>i;j--)
13             {
14                 //此处为<时其返回是从小到大排序，>时其返回从大到小
15                 if(disOrderArray[j] < disOrderArray[j-1])
16                 {
17                     temp = disOrderArray[j];
18                     disOrderArray[j] = disOrderArray[j-1];
19                     disOrderArray[j-1] = temp;
20                 }
21             }
22         }
23         return disOrderArray;
24     }

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

 1 void Bubble_1 ( int r[], int n) {  
 2     int i= n -1;  //初始时,最后位置保持不变  
 3     while ( i> 0) {   
 4         int pos= 0; //每趟开始时,无记录交换  
 5         for (int j= 0; j< i; j++)  
 6             if (r[j]> r[j+1]) {  
 7                 pos= j; //记录交换的位置   
 8                 int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
 9             }   
10         i= pos; //为下一趟排序作准备  
11      }   
12 }

 

二、快速排序

 

思想：通过一趟排序将待排记录分割成两个部分，其中一部分记录关键字均比另一部分记录的关键字小，则可以分别对这两部分关键字继续排序，以达到整个序列有序的目的。

时间复杂度：O(nlogn),最坏的情况下为O(n^2)

空间复杂度：O(1)

稳定性:不稳定

 1 /* 
 2 * 
 3 * 快速排序 
 4 * 
 5 * 思想:  
 6 * 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小, 
 7 * 则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的 
 8 *  
 9 * 本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base 
10 * 首先从序列最右边开始找比base小的 
11 * ,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大 
12 * 然后,从序列的最左边开始找比base大的 
13 * ,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小 
14 *  
15 * 循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归 
16 */  
17 public static int[] quickSort(int[] arr, int low, int heigh) {  
18     if(low < heigh)  
19     {  
20         int division = partition(arr, low, heigh);  
21           
22         quickSort(arr, low, division - 1);  
23           
24         quickSort(arr, division + 1, heigh);  
25     }  
26     return arr;  
27 }  
28   
29 // 分水岭,基位,左边的都比这个位置小,右边的都大  
30 private static int partition(int[] arr, int low, int heigh) {  
31     int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录  
32     while (low < heigh)  
33     {    
34         //更改下面两个while循环中的<=和>=，即可获取到从大到小排列  
35         //从表的两端交替向中间扫描，从小到大排列  
36         while (low < heigh && arr[heigh] >= base)  
37         {  
38             heigh--;  
39         }  
40           
41         // 如果高位小于base,base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大  
42         swap(arr, heigh, low);  
43           
44         while(low < heigh && arr[low] <= base)  
45         {  
46             low++;  
47         }  
48           
49         // 如果低位大有base,  
50         swap(arr, heigh, low);  
51     }  
52       
53     //现在low=heigh  
54     return low;  
55 }  
56   
57 //交换大小  
58 private static void swap(int[] arr, int heigh, int low) {  
59     int temp = arr[heigh];  
60     arr[heigh] = arr[low];  
61     arr[low] = temp;  
62 }

 

三、直接选择排序

思想：每一趟排序将会选择出最小的(或者最大的)值，顺序放在已排好序的数列的后面

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

 1 /** 
 2  * 直接选择排序 
 3  * 直接选择排序每一趟选择出最小的值 
 4  * @param arr 
 5  * @return 
 6  */  
 7 public static int[] selectionSort(int[] arr) {  
 8     for(int i=0;i<arr.length;i++)  
 9     {  
10         for(int j=i+1;j<arr.length;j++)  
11         {  
12             if(arr[i] > arr[j])  
13             {  
14                 int temp = arr[j];  
15                 arr[j] = arr[i];  
16                 arr[i] = temp;  
17             }  
18         }  
19     }  
20     return arr;  
21 }

简单选择排序的改进——二元选择排序

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

 1 void SelectSort(int r[],int n) {  
 2     int i ,j , min ,max, tmp;  
 3     for (i=1 ;i <= n/2;i++) {    
 4         // 做不超过n/2趟选择排序   
 5         min = i; max = i ; //分别记录最大和最小关键字记录位置  
 6         for (j= i+1; j<= n-i; j++) {  
 7             if (r[j] > r[max]) {   
 8                 max = j ; continue ;   
 9             }    
10             if (r[j]< r[min]) {   
11                 min = j ;   
12             }     
13       }    
14       //该交换操作还可分情况讨论以提高效率  
15       tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
16       tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   
17   
18     }   
19 }

 

 

四、堆排序

思想：堆排序利用这种堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素

时间复杂度：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

 1 /** 
 2  * 堆排序 
 3  * 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。 
 4  * @param arr 
 5  * @return 
 6  */  
 7 public static int[] heapSort(int[] arr) {  
 8     int i;  
 9     // 将arr构成一个大顶堆  
10     // 从 0 到 arr.length/2 ,这些都是有孩子的节点  
11     // 没孩子的节点构造大顶堆就无意义了  
12     for (i = arr.length / 2; i >= 0; i--)  
13     {  
14         heapAdjust(arr, i, arr.length - 1);  
15     }  
16     for (i = arr.length - 1; i > 0; i--)  
17     {  
18         swap(arr, 0, i);  
19         // 将arr[0...i-1] 重新构造成一个大顶堆  
20         heapAdjust(arr, 0, i - 1);  
21     }  
22     return arr;  
23 }  
24   
25 private static void heapAdjust(int[] arr, int s, int m) {  
26     int temp, j;  
27     temp = arr[s]; // 指向临时(相对与root节点)的根节点  
28     for (j = 2 * s; j <= m; j *= 2)   
29     {  
30         // 如果右节点比左节点大,当前节点移到右节点  
31         if (j < m && arr[j] < arr[j + 1])  
32         {  
33             // 指向右节点  
34             j++;  
35         }  
36         // 当前的父节点大于现在指向的节点  
37         // 不需要做任何处理  
38         if (temp >= arr[j])  
39         {  
40             break;  
41         }  
42           
43         // 当前的父节点小于其下的子节点  
44         // 换位置,把这个子节点替换到父节点  
45         // 当前这个位置,如果是叶子节点,则它应该是最小的(相对于它的祖先们)  
46         // 这个方法目的就是交换parent与children的值,构造大根堆  
47            
48         // 执行到这里表明当前节点的父节点(临时根节点小于当前的节点),  
49         // 把当前节点移到上面,换位置  
50         // arr[s]被覆盖无所谓,因为temp记了这个值(原来的根节点(相对的parent))  
51         arr[s] = arr[j];  
52            
53         // 现在把当前的这个元素,看做是临时的parent节点  
54         // 为了找到此时这个元素的孩子节点,看看是否有比当前这个值还大的  
55         // 最后s指向 当前遍历到的这个元素  
56         s = j;  
57     }  
58     arr[s] = temp;  
59 }

 

五、插入排序

思想：将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录增1的有序表。默认将第一个元素看为有序表，然后依次插入后边的元素

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

 1 /** 
 2  * 插入排序 
 3  * 思想:将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表， 
 4  * 默认将第一个元素看为有序表，一次插入后边的所欲元素 
 5  * 时间复杂度O(n^2) 
 6  * 空间复杂度O(1) 适用于记录数量小的 
 7  * @param arr 
 8  * @return 
 9  */  
10 public static int[] InsertSort(int[] arr) {  
11     //从小到大排列  
12     for(int i=1;i<arr.length;i++)  
13     {  
14         //待插入元素  
15         int temp = arr[i];  
16         int j;  
17         for(j=i-1;j>=0 && temp < arr[j];j--)  
18         {  
19             //待插入元素小于已有的，就将已有往后挪，直到元素大于插入元素或已经到序列最首端了  
20             arr[j+1] = arr[j];  
21         }  
22         arr[j+1] = temp;  
23     }  
24     return arr;  
25 }

 

六、希尔排序

思想：希尔排序也是插入排序的一种，是直接针对插入排序进行改进的，该方法又称为"缩小增量排序"。

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

 1 /** 
 2  * 希尔排序(缩小增量排序) 
 3  * 希尔排序也是插入排序的一种，只是其有增量，而且最后一次增量必须为1 
 4  * @param arr 
 5  * @return 
 6  */  
 7 public static int[] ShellInsert(int[] arr){  
 8     int step = arr.length/2; //取增量  
 9     //保证最后一个增量为1  
10     while(step >= 1)  
11     {  
12         for(int i=step;i<arr.length;i++)  
13         {  
14             int temp = arr[i];  
15             int j = 0;  
16               
17             //根插入排序的区别在这里  
18             for(j=i-step;j>=0 && temp<arr[j];j-=step)  
19             {  
20                 arr[j+step] = arr[j];  
21             }  
22             arr[j+step] = temp;  
23         }  
24         step /= 2;  
25     }  
26     return arr;  
27 }

 

七、归并排序

思想：归并排序是将两个或两个以上的有序表组合成一个有序表，该算法是采用分治法实现

时间复杂度：O(nlogn)

空间复杂度：O(n)

稳定性：稳定

 1 /** 
 2  * 归并排序 
 3  * 归并排序是将两个或两个以上的有序表组合成一个新的有序表 
 4  * 时间复杂度 O(nlog2n) 
 5  * @param arr 
 6  * @param tempArray 
 7  * @param left 
 8  * @param right 
 9  * @return 
10  */  
11 public static int[] mergeSort(int[] arr, int left,int right) {  
12     if (left < right)  
13     {  
14         // 取分割位置  
15         int middle = (left + right) / 2;  
16         // 递归划分数组左序列  
17         mergeSort(arr, left, middle);  
18         // 递归划分数组右序列  
19         mergeSort(arr, middle+1, right);  
20         //将左数组和右数组进行归并  
21         Merge(arr, left, middle, right);  
22     }  
23     return arr;  
24 }  
25   
26 private static void Merge(int[] arr, int left, int middle,int right) {  
27     int[] tempArray = new int[arr.length];    
28     int leftEnd = middle;  
29     int rightStart = middle+1;  
30     // 临时数组的下标  
31     int tempIndex = left;  
32     int tmp = left;  
33       
34     // 先循环两个区间段都没有结束的情况  
35     while ((left <= leftEnd) && (rightStart <= right))  
36     {  
37         // 左边的比右边的小,先插入左边的  
38         if (arr[left] < arr[rightStart])  
39         {  
40             tempArray[tempIndex++] = arr[left++];  
41         }  
42         else  
43         {  
44             tempArray[tempIndex++] = arr[rightStart++];  
45         }  
46     }  
47       
48     // 判断左序列是否结束  
49     while (left <= leftEnd)  
50     {  
51         tempArray[tempIndex++] = arr[left++];  
52     }  
53       
54     // 判断右序列是否结束  
55     while (rightStart <= right)  
56     {  
57         tempArray[tempIndex++] = arr[rightStart++];  
58     }  
59       
60     // 将临时数组中的内容拷贝回原数组中    
61        // （原left-right范围的内容被复制回原数组）  
62     while (tmp <= right) {    
63            arr[tmp] = tempArray[tmp++];    
64        }   
65 }

 

八、基数排序

思想：基数是按照低位先排序，然后收集；再按高位排序，然后再收集，依次类推，直到最高位。

注:表示关键词分类到radix(基数)个盒子，在关键词为数字时，基数为10，当关键词为字母时，基数为26

时间复杂度：O(n+d)

空间复杂度：O(n)

稳定性：稳定

 1 /** 
 2  * 基数排序 
 3  * @radix 基数 表示  按关键词分类到radix(基数)个盒子  在关键词为数字时，基数为10 
 4  * @d 排序元素的位数   
 5  * @return 
 6  */  
 7 public static int[] RadixSort(int[] arr, int radix, int d){  
 8     //用于暂存元素  
 9     int[] temp = new int[arr.length];  
10     //用于计数排序  
11     int[] count = new int[radix];  
12     int divide = 1;  
13       
14     for(int i=0;i<d;i++)  
15     {  
16         System.arraycopy(arr, 0, temp, 0, arr.length);  
17           
18         // 重置count数组，开始统计下一个关键字    
19         Arrays.fill(count, 0);  
20           
21         // 计算每个待排序数据的子关键字    
22         for(int j=0;j<arr.length;j++)  
23         {  
24             int tempKey = (temp[j]/divide)%radix;  
25             count[tempKey]++;  
26         }  
27           
28         for(int j=1;j<radix;j++)  
29         {  
30             count[j] = count[j] + count[j-1];  
31         }  
32           
33         // 按子关键字对指定的数据进行排序    
34         for(int j=arr.length-1;j>=0;j--)  
35         {  
36             int tempKey = (temp[j]/divide)%radix;  
37             count[tempKey]--;  
38             arr[count[tempKey]] = temp[j];  
39         }  
40           
41         divide = divide * radix;  
42     }  
43     return arr;  
44 }

 

添加一个二分查找算法：类似于折半查找算法

时间复杂度：O(logn)

 1 /** 
 2  * 二分查找 
 3  * @param arr 
 4  * @param searchnum 待查找元素 
 5  * @return 
 6  */  
 7 public static int BSearch(int[] arr, int searchnum){  
 8     int low = 0;  
 9     int high = arr.length-1;  
10     while(low<=high)  
11     {  
12         int m = (low+high)/2;  
13         if(searchnum == arr[m])  
14         {  
15             return m;  
16         }  
17         else if(searchnum < arr[m])  
18         {  
19             high = m-1;  
20         }  
21         else  
22         {  
23             low = m+1;  
24         }  
25     }  
26     return -1;  
27 }

 

 

一、冒泡排序

思想：重复走访过要排序的序列，一次比较两个元素，如果他们的顺序错误就将他们进行交换，一次冒上来的是最小的，其次是第二小。

时间复杂度：O(n^2)

空间复杂度:O(1)

稳定性：稳定

1.

 

[java]  view plain  copy
 
  1. /** 
  2.      * 冒泡排序 
  3.      * @param disOrderArray 
  4.      * @return 
  5.      */  
  6.     public static int[] BubbleSort(int[] disOrderArray) {  
  7.         int temp;  
  8.         // 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）  
  9.         for(int i=0;i<disOrderArray.length-1;i++)  
  10.         {  
  11.             // 把最小的数交换着"冒泡"的相对的最上边,一次冒上来的是最小的,其次是第二小的.  
  12.             for(int j=disOrderArray.length-1;j>i;j--)  
  13.             {  
  14.                 //此处为<时其返回是从小到大排序，>时其返回从大到小  
  15.                 if(disOrderArray[j] < disOrderArray[j-1])  
  16.                 {  
  17.                     temp = disOrderArray[j];  
  18.                     disOrderArray[j] = disOrderArray[j-1];  
  19.                     disOrderArray[j-1] = temp;  
  20.                 }  
  21.             }  
  22.         }  
  23.         return disOrderArray;  
  24.     }  


二、快速排序

 

思想：通过一趟排序将待排记录分割成两个部分，其中一部分记录关键字均比另一部分记录的关键字小，则可以分别对这两部分关键字继续排序，以达到整个序列有序的目的。

时间复杂度：O(nlogn),最坏的情况下为O(n^2)

空间复杂度：O(1)

稳定性:不稳定

 

[java]  view plain  copy
 
  1. /* 
  2. * 
  3. * 快速排序 
  4. * 
  5. * 思想:  
  6. * 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小, 
  7. * 则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的 
  8. *  
  9. * 本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base 
  10. * 首先从序列最右边开始找比base小的 
  11. * ,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大 
  12. * 然后,从序列的最左边开始找比base大的 
  13. * ,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小 
  14. *  
  15. * 循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归 
  16. */  
  17. public static int[] quickSort(int[] arr, int low, int heigh) {  
  18.     if(low < heigh)  
  19.     {  
  20.         int division = partition(arr, low, heigh);  
  21.           
  22.         quickSort(arr, low, division - 1);  
  23.           
  24.         quickSort(arr, division + 1, heigh);  
  25.     }  
  26.     return arr;  
  27. }  
  28.   
  29. // 分水岭,基位,左边的都比这个位置小,右边的都大  
  30. private static int partition(int[] arr, int low, int heigh) {  
  31.     int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录  
  32.     while (low < heigh)  
  33.     {    
  34.         //更改下面两个while循环中的<=和>=，即可获取到从大到小排列  
  35.         //从表的两端交替向中间扫描，从小到大排列  
  36.         while (low < heigh && arr[heigh] >= base)  
  37.         {  
  38.             heigh--;  
  39.         }  
  40.           
  41.         // 如果高位小于base,base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大  
  42.         swap(arr, heigh, low);  
  43.           
  44.         while(low < heigh && arr[low] <= base)  
  45.         {  
  46.             low++;  
  47.         }  
  48.           
  49.         // 如果低位大有base,  
  50.         swap(arr, heigh, low);  
  51.     }  
  52.       
  53.     //现在low=heigh  
  54.     return low;  
  55. }  
  56.   
  57. //交换大小  
  58. private static void swap(int[] arr, int heigh, int low) {  
  59.     int temp = arr[heigh];  
  60.     arr[heigh] = arr[low];  
  61.     arr[low] = temp;  
  62. }  


三、直接选择排序:

 

思想：每一趟排序将会选择出最小的(或者最大的)值，顺序放在已排好序的数列的后面

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 直接选择排序 
  3.  * 直接选择排序每一趟选择出最小的值 
  4.  * @param arr 
  5.  * @return 
  6.  */  
  7. public static int[] selectionSort(int[] arr) {  
  8.     for(int i=0;i<arr.length;i++)  
  9.     {  
  10.         for(int j=i+1;j<arr.length;j++)  
  11.         {  
  12.             if(arr[i] > arr[j])  
  13.             {  
  14.                 int temp = arr[j];  
  15.                 arr[j] = arr[i];  
  16.                 arr[i] = temp;  
  17.             }  
  18.         }  
  19.     }  
  20.     return arr;  
  21. }  


四、堆排序

 

思想：堆排序利用这种堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素

时间复杂度：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 堆排序 
  3.  * 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。 
  4.  * @param arr 
  5.  * @return 
  6.  */  
  7. public static int[] heapSort(int[] arr) {  
  8.     int i;  
  9.     // 将arr构成一个大顶堆  
  10.     // 从 0 到 arr.length/2 ,这些都是有孩子的节点  
  11.     // 没孩子的节点构造大顶堆就无意义了  
  12.     for (i = arr.length / 2; i >= 0; i--)  
  13.     {  
  14.         heapAdjust(arr, i, arr.length - 1);  
  15.     }  
  16.     for (i = arr.length - 1; i > 0; i--)  
  17.     {  
  18.         swap(arr, 0, i);  
  19.         // 将arr[0...i-1] 重新构造成一个大顶堆  
  20.         heapAdjust(arr, 0, i - 1);  
  21.     }  
  22.     return arr;  
  23. }  
  24.   
  25. private static void heapAdjust(int[] arr, int s, int m) {  
  26.     int temp, j;  
  27.     temp = arr[s]; // 指向临时(相对与root节点)的根节点  
  28.     for (j = 2 * s; j <= m; j *= 2)   
  29.     {  
  30.         // 如果右节点比左节点大,当前节点移到右节点  
  31.         if (j < m && arr[j] < arr[j + 1])  
  32.         {  
  33.             // 指向右节点  
  34.             j++;  
  35.         }  
  36.         // 当前的父节点大于现在指向的节点  
  37.         // 不需要做任何处理  
  38.         if (temp >= arr[j])  
  39.         {  
  40.             break;  
  41.         }  
  42.           
  43.         // 当前的父节点小于其下的子节点  
  44.         // 换位置,把这个子节点替换到父节点  
  45.         // 当前这个位置,如果是叶子节点,则它应该是最小的(相对于它的祖先们)  
  46.         // 这个方法目的就是交换parent与children的值,构造大根堆  
  47.            
  48.         // 执行到这里表明当前节点的父节点(临时根节点小于当前的节点),  
  49.         // 把当前节点移到上面,换位置  
  50.         // arr[s]被覆盖无所谓,因为temp记了这个值(原来的根节点(相对的parent))  
  51.         arr[s] = arr[j];  
  52.            
  53.         // 现在把当前的这个元素,看做是临时的parent节点  
  54.         // 为了找到此时这个元素的孩子节点,看看是否有比当前这个值还大的  
  55.         // 最后s指向 当前遍历到的这个元素  
  56.         s = j;  
  57.     }  
  58.     arr[s] = temp;  
  59. }  



 


五、插入排序

思想：将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录增1的有序表。默认将第一个元素看为有序表，然后依次插入后边的元素

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 插入排序 
  3.  * 思想:将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表， 
  4.  * 默认将第一个元素看为有序表，一次插入后边的所欲元素 
  5.  * 时间复杂度O(n^2) 
  6.  * 空间复杂度O(1) 适用于记录数量小的 
  7.  * @param arr 
  8.  * @return 
  9.  */  
  10. public static int[] InsertSort(int[] arr) {  
  11.     //从小到大排列  
  12.     for(int i=1;i<arr.length;i++)  
  13.     {  
  14.         //待插入元素  
  15.         int temp = arr[i];  
  16.         int j;  
  17.         for(j=i-1;j>=0 && temp < arr[j];j--)  
  18.         {  
  19.             //待插入元素小于已有的，就将已有往后挪，直到元素大于插入元素或已经到序列最首端了  
  20.             arr[j+1] = arr[j];  
  21.         }  
  22.         arr[j+1] = temp;  
  23.     }  
  24.     return arr;  
  25. }  


六、折半插入排序

 

思想：折半插入排序是基于直接插入排序进行改写的，其可以减少"移动"和"比较"的次数

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 折半插入排序 
  3.  * 优点:可以减少"比较"和"移动"的次数 
  4.  * @param arr 
  5.  * @return 
  6.  */  
  7. public static int[] BInsertSort(int[] arr){  
  8.     for(int i=1;i<arr.length;i++)  
  9.     {  
  10.         //待插入元素  
  11.         int temp = arr[i];  
  12.         int j;  
  13.         int low = 0, high = i-1;  
  14.         while(low <= high)  //在arr[low..high]中折半查找有序插入的位置  
  15.         {  
  16.             int m = (low + high)/2;//折半  
  17.             if(temp < arr[m])  
  18.             {  
  19.                 high = m-1;  //插入点在低半区  
  20.             }  
  21.             else  
  22.             {  
  23.                 low = m+1;  //插入点在高半区  
  24.             }  
  25.         }  
  26.           
  27.         //记录后移  
  28.         for(j=i-1;j>=high+1;j--)  
  29.         {  
  30.             arr[j+1] = arr[j];  
  31.         }  
  32.         arr[j+1] = temp;  
  33.     }  
  34.     return arr;  
  35. }  


七、希尔排序：

 

思想：希尔排序也是插入排序的一种，是直接针对插入排序进行改进的，该方法又称为"缩小增量排序"。

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 希尔排序(缩小增量排序) 
  3.  * 希尔排序也是插入排序的一种，只是其有增量，而且最后一次增量必须为1 
  4.  * @param arr 
  5.  * @return 
  6.  */  
  7. public static int[] ShellInsert(int[] arr){  
  8.     int step = arr.length/2; //取增量  
  9.     //保证最后一个增量为1  
  10.     while(step >= 1)  
  11.     {  
  12.         for(int i=step;i<arr.length;i++)  
  13.         {  
  14.             int temp = arr[i];  
  15.             int j = 0;  
  16.               
  17.             //根插入排序的区别在这里  
  18.             for(j=i-step;j>=0 && temp<arr[j];j-=step)  
  19.             {  
  20.                 arr[j+step] = arr[j];  
  21.             }  
  22.             arr[j+step] = temp;  
  23.         }  
  24.         step /= 2;  
  25.     }  
  26.     return arr;  
  27. }  


八、归并排序

 

思想：归并排序是将两个或两个以上的有序表组合成一个有序表，该算法是采用分治法实现

时间复杂度：O(nlogn)

空间复杂度：O(n)

稳定性：稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 归并排序 
  3.  * 归并排序是将两个或两个以上的有序表组合成一个新的有序表 
  4.  * 时间复杂度 O(nlog2n) 
  5.  * @param arr 
  6.  * @param tempArray 
  7.  * @param left 
  8.  * @param right 
  9.  * @return 
  10.  */  
  11. public static int[] mergeSort(int[] arr, int left,int right) {  
  12.     if (left < right)  
  13.     {  
  14.         // 取分割位置  
  15.         int middle = (left + right) / 2;  
  16.         // 递归划分数组左序列  
  17.         mergeSort(arr, left, middle);  
  18.         // 递归划分数组右序列  
  19.         mergeSort(arr, middle+1, right);  
  20.         //将左数组和右数组进行归并  
  21.         Merge(arr, left, middle, right);  
  22.     }  
  23.     return arr;  
  24. }  
  25.   
  26. private static void Merge(int[] arr, int left, int middle,int right) {  
  27.     int[] tempArray = new int[arr.length];    
  28.     int leftEnd = middle;  
  29.     int rightStart = middle+1;  
  30.     // 临时数组的下标  
  31.     int tempIndex = left;  
  32.     int tmp = left;  
  33.       
  34.     // 先循环两个区间段都没有结束的情况  
  35.     while ((left <= leftEnd) && (rightStart <= right))  
  36.     {  
  37.         // 左边的比右边的小,先插入左边的  
  38.         if (arr[left] < arr[rightStart])  
  39.         {  
  40.             tempArray[tempIndex++] = arr[left++];  
  41.         }  
  42.         else  
  43.         {  
  44.             tempArray[tempIndex++] = arr[rightStart++];  
  45.         }  
  46.     }  
  47.       
  48.     // 判断左序列是否结束  
  49.     while (left <= leftEnd)  
  50.     {  
  51.         tempArray[tempIndex++] = arr[left++];  
  52.     }  
  53.       
  54.     // 判断右序列是否结束  
  55.     while (rightStart <= right)  
  56.     {  
  57.         tempArray[tempIndex++] = arr[rightStart++];  
  58.     }  
  59.       
  60.     // 将临时数组中的内容拷贝回原数组中    
  61.        // （原left-right范围的内容被复制回原数组）  
  62.     while (tmp <= right) {    
  63.            arr[tmp] = tempArray[tmp++];    
  64.        }   
  65. }  


九、基数排序

 

思想：基数是按照低位先排序，然后收集；再按高位排序，然后再收集，依次类推，直到最高位。

注:表示关键词分类到radix(基数)个盒子，在关键词为数字时，基数为10，当关键词为字母时，基数为26

时间复杂度：O(n+d)

空间复杂度：O(n)

稳定性：稳定

 

[java]  view plain  copy
 
  1. /** 
  2.  * 基数排序 
  3.  * @radix 基数 表示  按关键词分类到radix(基数)个盒子  在关键词为数字时，基数为10 
  4.  * @d 排序元素的位数   
  5.  * @return 
  6.  */  
  7. public static int[] RadixSort(int[] arr, int radix, int d){  
  8.     //用于暂存元素  
  9.     int[] temp = new int[arr.length];  
  10.     //用于计数排序  
  11.     int[] count = new int[radix];  
  12.     int divide = 1;  
  13.       
  14.     for(int i=0;i<d;i++)  
  15.     {  
  16.         System.arraycopy(arr, 0, temp, 0, arr.length);  
  17.           
  18.         // 重置count数组，开始统计下一个关键字    
  19.         Arrays.fill(count, 0);  
  20.           
  21.         // 计算每个待排序数据的子关键字    
  22.         for(int j=0;j<arr.length;j++)  
  23.         {  
  24.             int tempKey = (temp[j]/divide)%radix;  
  25.             count[tempKey]++;  
  26.         }  
  27.           
  28.         for(int j=1;j<radix;j++)  
  29.         {  
  30.             count[j] = count[j] + count[j-1];  
  31.         }  
  32.           
  33.         // 按子关键字对指定的数据进行排序    
  34.         for(int j=arr.length-1;j>=0;j--)  
  35.         {  
  36.             int tempKey = (temp[j]/divide)%radix;  
  37.             count[tempKey]--;  
  38.             arr[count[tempKey]] = temp[j];  
  39.         }  
  40.           
  41.         divide = divide * radix;  
  42.     }  
  43.     return arr;  
  44. }  



 

 

[java]  view plain  copy
 
  1. public static void main(String[] args) {  
  2.         //基础默认从小到大排列  
  3. //      int[] disOrderArray = {3,1,5,7,0};  
  4.         //冒泡排序  
  5. //      disOrderArray = BubbleSort(disOrderArray);  
  6.           
  7.         //快速排序  
  8. //      disOrderArray = quickSort(disOrderArray, 0, disOrderArray.length-1);  
  9.           
  10.         //直接选择排序  
  11. //      disOrderArray = selectionSort(disOrderArray);  
  12.           
  13.         //堆排序  
  14. //      disOrderArray = heapSort(disOrderArray);  
  15.           
  16.         //直接插入排序  
  17. //      disOrderArray = InsertSort(disOrderArray);  
  18.           
  19.         //折半插入排序(二分查找排序)  
  20. //      disOrderArray = BInsertSort(disOrderArray);  
  21.           
  22.         //希尔排序  
  23. //      disOrderArray = ShellInsert(disOrderArray);  
  24.           
  25.         //归并排序  
  26. //      disOrderArray = mergeSort(disOrderArray, 0, disOrderArray.length-1);  
  27.           
  28.         //基数排序  
  29.         int[] disOrderArray = {3,2,3,2,5,333,45566,2345678,78,990,12,432,56};  
  30.           
  31.         disOrderArray = RadixSort(disOrderArray, 10, 7);  
  32.         for(int i=0;i<disOrderArray.length;i++)  
  33.         {  
  34.             System.out.print(disOrderArray[i]+" ");  
  35.         }  
  36.     }  


数据结构基本的排序算法基本都全了。

 

 

添加一个二分查找算法：类似于折半查找算法

时间复杂度：O(logn)

 

[java]  view plain  copy
 
  1. /** 
  2.  * 二分查找 
  3.  * @param arr 
  4.  * @param searchnum 待查找元素 
  5.  * @return 
  6.  */  
  7. public static int BSearch(int[] arr, int searchnum){  
  8.     int low = 0;  
  9.     int high = arr.length-1;  
  10.     while(low<=high)  
  11.     {  
  12.         int m = (low+high)/2;  
  13.         if(searchnum == arr[m])  
  14.         {  
  15.             return m;  
  16.         }  
  17.         else if(searchnum < arr[m])  
  18.         {  
  19.             high = m-1;  
  20.         }  
  21.         else  
  22.         {  
  23.             low = m+1;  
  24.         }  
  25.     }  
  26.     return -1;  
  27. }  

 

转载于:https://www.cnblogs.com/xuzekun/p/7479279.html

相关文章：

  • XML与JSON的区别
  • Bootstrap学习笔记（五）-----按钮
  • vue2.0项目引入element-ui
  • CODEVS 3500
  • bzoj 1593: [Usaco2008 Feb]Hotel 旅馆
  • Struts2 返回Json
  • centos6.5 iptables结合ipset批量屏蔽ip
  • Android NDK开发, 为App增加一个NDK模块
  • Cloudera与MongoDB共赴大数据“爱河”
  • shell三剑客之sed命令使用详解
  • CloudCC:如何用CRM更快更多抓取客源？
  • iOS学习路线
  • 野心勃勃的NoSQL新贵 MongoDB应用实战(1)
  • Palo Alto Networks的下一代安全方法论
  • 经典算法题每日演练——第二题 五家共井
  • Angular2开发踩坑系列-生产环境编译
  • avalon2.2的VM生成过程
  • iBatis和MyBatis在使用ResultMap对应关系时的区别
  • IOS评论框不贴底（ios12新bug）
  • javascript 哈希表
  • Java面向对象及其三大特征
  • Koa2 之文件上传下载
  • k个最大的数及变种小结
  • MySQL数据库运维之数据恢复
  • PAT A1050
  • Python_OOP
  • Spring Boot快速入门（一）：Hello Spring Boot
  • spring boot下thymeleaf全局静态变量配置
  • Vue 动态创建 component
  • 如何编写一个可升级的智能合约
  • 责任链模式的两种实现
  • 走向全栈之MongoDB的使用
  • # 数据结构
  • #pragma once
  • $emit传递多个参数_PPC和MIPS指令集下二进制代码中函数参数个数的识别方法
  • （2）(2.10) LTM telemetry
  • (70min)字节暑假实习二面（已挂）
  • (javascript)再说document.body.scrollTop的使用问题
  • （翻译）Entity Framework技巧系列之七 - Tip 26 – 28
  • (转)拼包函数及网络封包的异常处理(含代码)
  • **PyTorch月学习计划 - 第一周；第6-7天: 自动梯度（Autograd）**
  • .cfg\.dat\.mak（持续补充）
  • .net core 源码_ASP.NET Core之Identity源码学习
  • .NET Core6.0 MVC+layui+SqlSugar 简单增删改查
  • .Net Remoting常用部署结构
  • .NET Standard / dotnet-core / net472 —— .NET 究竟应该如何大小写？
  • .Net 代码性能 - (1)
  • .NET企业级应用架构设计系列之应用服务器
  • 。Net下Windows服务程序开发疑惑
  • [383] 赎金信 js
  • [ES-5.6.12] x-pack ssl
  • [Java]快速入门优先队列(堆)手撕相关面试题
  • [JAVA设计模式]第二部分：创建模式
  • [jQuery]10 Things I Learned from the jQuery Source
  • [linux][调度] 内核抢占入门 —— 高优先级线程被唤醒时会立即抢占当前线程吗 ?