首页 > 代码库 > 数据结构与算法——排序算法

数据结构与算法——排序算法

2024-07-05 10:17:53   235人阅读

常见排序算法主要有：

  • 插入排序（直接插入排序、希尔排序）
  • 选择排序（直接选择排序、堆排序）
  • 交换排序（冒泡排序、快速排序）
  • 归并排序
  • 基数排序
  • 外部排序

一.直接插入排序

算法思想：在一个待排序列中，从第二个元素开始，依次进行排序，每次都将待排序元素从后往前，依次与前面的元素进行比较，从而将带排序元素移动到一个合适的位置，直到最后一个待排序元素移动到合适位置，则排序完成。
算法特点：最好情况下时间复杂度O(n)，最坏情况下时间复杂度O(n2)，稳定排序算法

二.希尔排序

希尔排序算法基础：待排序元素越有序，直接插入排序开销时间越小，希尔排序利用了这一思想。
算法思想：将待排序元素分成若干个小组，然后对每个小组进行直接插入排序。一次排序完成之后，将小组合并成更大的小组，再进行直接插入排序，重复上述操作直到最后只有一个小组为止，算法结束。
 
算法特点：时间复杂度约为O(n(lbn)2)，不稳定排序算法
 1 /**
 2   * 希尔排序
 3   * @param array:待排序数组
 4   * @param n：循环的数量
 5   */
 6  public void shellSort(int[] array){
 7  
 8   //确定执行简单插入排序的轮询次数，log2
 9   int n = (int) (Math.log10(array.length) / Math.log10(2));
10  
11   //每次轮询设置的简单插入排序的成员个数满足2的幂，...8,4,2,1(逆序)
12   for(int i = n; i >= 0; i--){
13      int span = (int) Math.pow(2, i);
14      for(int j = 0; j < array.length - span; j++){
15      　　for(int k = j + span; k < array.length; k += span){
16      　　for(int l = k; l >= span; l -= span){
17       　　　　//使用简单插入排序
18       　　　　if(array[l] < array[l - span]){
19       　　　　int temp = array[l];
20       　　　　array[l] = array[l - span];
21       　　　　array[l - span] = temp;
22       　　　　}else{
23        　　　　　　break;
24       　　　　}
25      　　　　}      
26     　　}
27    　　}
28   　　}
29  }

三.直接选择排序

算法思想：每次都从未排序集合中选择相对最小（最大）的元素与未排序集合的第一个元素交换位置，直到未排序集合的个数变为0；
算法特点：时间复杂度O(n2)，不稳定

四.堆排序

基本概念：
  1. 最大堆：双亲节点大于孩子节点形式的完全二叉树。排序对应非递减序列。
  2. 最小堆：双亲节点小于孩子节点形式的完全二叉树。排序对应非递增序列。
  3. 满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有的叶子节点都在同一层上，则称为满二叉树。
  4. 完全二叉树：就是将满二叉树从按照层序遍历得到的序列的逆序删除一定个数的节点（大于等于0）后得到的二叉树。所以满二叉树也是完全二叉树。
  5. 树的表示方法：
  • 双亲表示法。每一个节点中存有父亲节点的信息，易于查父亲节点，但查孩子节点教复杂。
  • 孩子表示法。每一个节点都存有自己孩子节点的信息，易于查孩子节点，但查父亲节点较复杂。
  • 双亲孩子表示法。每一个节点都存有父亲和孩子的信息，查父亲和孩子都比较容易，但是不易于在上面进行操作。
  • 孩子兄弟表示法（※推荐使用）。如下图：

　　　　

  •  非递归二叉树遍历：先序遍历可以借助堆栈来辅助实现，层序遍历可以借助队列来辅助实现。　　　　　　　　　　　
算法思想：
算法特点：
 1 package day20140520;
 2 
 3 import java.util.ArrayList;
 4 import java.util.LinkedList;
 5 import java.util.Scanner;
 6 
 7 public class HeapSorting {
 8 
 9     /**
10      * 创建最大堆
11      * @param a
12      * @param i
13      */
14     private static void buildMaxHeap(ArrayList<Integer> a, int i) {
15         if(i < 0)
16             return;
17         int l = 2 * i + 1;
18         int r = 2 * i + 2;        
19         if (l < a.size()) {            
20             if (r < a.size()) {
21                 int max = Math.max(a.get(l), a.get(r));
22                 if (max > a.get(i)) {
23                     if (a.get(l) == max) {
24                         a.set(l, a.get(i));
25                         a.set(i, max);
26                         buildMaxHeap(a, l);
27                     } else {
28                         a.set(r, a.get(i));
29                         a.set(i, max);
30                         buildMaxHeap(a, r);
31                     }
32                 } else {
33                     buildMaxHeap(a, --i);
34                 }
35 
36             } else {
37                 if (a.get(i) < a.get(l)) {
38                     int temp = a.get(i);
39                     a.set(i, a.get(l));
40                     a.set(l, temp);
41                     buildMaxHeap(a, l);
42                 } else {
43                     buildMaxHeap(a, --i);
44                 }
45             }
46         } else {
47             --i;
48             buildMaxHeap(a, i);
49         }
50     }
51     
52     /**
53      * 堆排序
54      * @param input
55      */
56     private static LinkedList<Integer> heapSort(ArrayList<Integer> input){
57         LinkedList<Integer> list = null;
58         if(input != null){
59             list = new LinkedList<Integer>();
60         }
61         while(input.size() > 0){
62             int startIndex = input.size() / 2 - 1;
63             buildMaxHeap(input, startIndex);  //构建最大堆
64             //交换堆中第一个和最后一个元素
65             int lastIndex = input.size() - 1;
66             int temp = input.get(lastIndex);
67             input.set(lastIndex, input.get(0));
68             input.set(0, temp);
69             //截取堆中的最后一个元素
70             list.addFirst(input.remove(lastIndex));
71         }            
72         return list;
73     }
74 
75     public static void main(String[] args) {
76         
77         //4 1 3 2 16 9 10 14 8 7
78         Scanner sc = new Scanner(System.in);
79         String in_str = sc.nextLine().trim().replaceAll(" +", " ");
80         String[] in_str_arr = in_str.split(" ");
81         ArrayList<Integer> input = new ArrayList<Integer>();
82         for (int i = 0; i < in_str_arr.length; i++) {
83             input.add(Integer.parseInt(in_str_arr[i]));
84         }
85 
86         LinkedList<Integer> list = HeapSorting.heapSort(input);
87         if(list != null)
88             System.out.println(list);
89     }
90 }　　　
 

持续更新中......

五.冒泡排序

六.快速排序

七.归并排序

八.基数排序

九.外部排序


联系
我们