Android-算法

发表于   |   分类于   |  

前言

Linus Benedict Torvalds : RTFSC – Read The Funning Source Code

排序算法

快速排序

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

堆排序的平均时间复杂度为Ο(nlogn)。

具体操作:

  1. 从数列中挑出一个元素，称为 “基准”(pivot)。
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void quickSort(int[] a, int low, int high) {
    int p = get(a, low, high);
    quickSort(a, low, p - 1);
    quickSort(a, p + 1, high);
}
int get(int[] a, int low, int high) {
    int compare = a[low];
    
    while (low < high) { //无论如何置换, 被置换的都包含compare的值
        while (low < high && a[high] >= compare) {
            high--;
        }
        
        //在 low<high 的情况下找到a[high]<compare并置换 
        int temp = a[low];
        a[low] = a[high];
        a[high] = temp;
        
        while (low < high && a[low] <= compare) {
            low++;
        }
        
        //在 low<high 的情况下找到a[low]>compare并置换 
        temp = a[low];
        a[low] = a[high];
        a[high] = temp;
    }
    return low; //while(low==hight)停止循环, 并返回枢轴位置 
}

详细过程
快速排序

堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。

堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆排序的平均时间复杂度为Ο(nlogn)。

具体操作:

  1. 从数列中挑出一个元素，称为 “基准”(pivot)。
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void HeapAdjust(int H[], int start, int end) {
    int temp = H[start];
    for (int i = 2 * start + 1; i <= end; i *= 2) {
        //因为假设根结点的序号为0而不是1，所以i结点左孩子和右孩子分别为2i+1和2i+2
        if (i < end && H[i] < H[i + 1])//左右孩子的比较
        {
            ++i;//i为较大的记录的下标
        }
        
        if (temp > H[i])//左右孩子中获胜者与父亲的比较
        {
            break;
        }
        //将孩子结点上位，则以孩子结点的位置进行下一轮的筛选
        H[start] = H[i];
        start = i;
        
    }
    H[start] = temp; //插入最开始不和谐的元素
}
void HeapSort(int A[], int n) {
    //先建立大顶堆
    for (int i = n / 2; i >= 0; --i) {
        HeapAdjust(A, i, n);
    }
    //进行排序
    for (int i = n - 1; i > 0; --i) {
        //最后一个元素和第一元素进行交换
        int temp = A[i];
        A[i] = A[0];
        A[0] = temp;
        
        //然后将剩下的无序元素继续调整为大顶堆
        HeapAdjust(A, 0, i - 1);
    }
}

详细过程
堆排序

归并排序

建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

归并排序的平均时间复杂度为O(nlogn)

具体操作:

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置。
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针超出序列尾。
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 二路归并
 * 原理：将两个有序表合并和一个有序表
 *
 * @param a
 * @param s 第一个有序表的起始下标
 * @param m 第二个有序表的起始下标
 * @param t 第二个有序表的结束小标
 */
private static void merge(int[] a, int s, int m, int t) {
    int[] tmp = new int[t - s + 1];
    int i = s, j = m, k = 0;
    while (i < m && j <= t) {
        if (a[i] <= a[j]) {
            tmp[k] = a[i];
            k++;
            i++;
        } else {
            tmp[k] = a[j];
            j++;
            k++;
        }
    }
    while (i < m) {
        tmp[k] = a[i];
        i++;
        k++;
    }
    while (j <= t) {
        tmp[k] = a[j];
        j++;
        k++;
    }
    System.arraycopy(tmp, 0, a, s, tmp.length);
}
/**
 * @param a
 * @param s
 * @param len 每次归并的有序集合的长度
 */
public static void mergeSort(int[] a, int s, int len) {
    int size = a.length;
    int mid = size / (len << 1);
    int c = size & ((len << 1) - 1);
    //-------归并到只剩一个有序集合的时候结束算法-------//
    if (mid == 0) {
        return;
    }
    //------进行一趟归并排序-------//
    for (int i = 0; i < mid; ++i) {
        s = i * 2 * len;
        merge(a, s, s + len, (len << 1) + s - 1);
    }
    //-------将剩下的数和倒数一个有序集合归并-------//
    if (c != 0) {
        merge(a, size - c - 2 * len, size - c, size - 1);
    }
    //-------递归执行下一趟归并排序------//
    mergeSort(a, 0, 2 * len);
}

详细过程
归并排序

插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序法。

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序的平均时间复杂度为O(n^2)

具体操作:

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
int n = sizeof(A) / sizeof(int);
int i, j, get;
for (i = 1; i < n; i++)             // 类似抓扑克牌排序
{
    get = A[i];                     // 右手抓到一张扑克牌
    j = i - 1;                      // 拿在左手上的牌总是排序好的
    while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较
    {
        A[j + 1] = A[j];            // 如果该手牌比抓到的牌大,就将其右移
        j--;
    }
    A[j + 1] = get;                 // 直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)
}

详细过程
插入排序
插入排序2

二分插入排序

二分插入排序本质上就是在插入排序的查找阶段在已排好的序列中实现二分查找法找到插入点的优化。

具体操作:

  1. 计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
  2. 在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方；
  3. 确定位置之后，将整个序列后移，并将元素插入到相应位置。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序
int n = sizeof(A) / sizeof(int);
int i, j, get, left, right, middle;
for (i = 1; i < n; i++)                 // 类似抓扑克牌排序
{
    get = A[i];                         // 右手抓到一张扑克牌
    left = 0;                           // 拿在左手上的牌总是排序好的,所以可以用二分法
    right = i - 1;                      // 手牌左右边界进行初始化
    while (left <= right)               // 采用二分法定位新牌的位置
    {
        middle = (left + right) / 2;
        if (A[middle] > get)
            right = middle - 1;
        else
            left = middle + 1;
    }
    for (j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
    {
        A[j + 1] = A[j];            
    }
    A[left] = get;                    // 将抓到的牌插入手牌
}

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序的平均时间复杂度为O(Nlog2N)

具体操作:

  1. 将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序。
  2. 依次缩减增量再进行排序。
  3. 待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int gap = list.length / 2;
 
while (1 <= gap) {
    // 把距离为 gap 的元素编为一个组，扫描所有组
    for (int i = gap; i < list.length; i++) {
        int j = 0;
        int temp = list[i];
        // 对距离为 gap 的元素组进行排序
        for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
            list[j + gap] = list[j];
        }
        list[j + gap] = temp;
    }
    gap = gap / 2; // 减小增量
}

详细过程
希尔排序

冒泡排序

冒泡排序是一种极其简单的排序算法。它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的平均时间复杂度为O(n^2)

具体操作:

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void sort(int[] a)
{
    int temp = 0;
    for (int i = a.length - 1; i > 0; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (a[j + 1] < a[j])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

详细过程
冒泡排序

鸡尾酒排序

鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。

冒泡排序的平均时间复杂度为O(n²)

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };   // 从小到大定向冒泡排序
int n = sizeof(A) / sizeof(int);                
int left = 0;                           // 初始化边界
int right = n - 1;
while (left < right)
{
    for (int i = left; i < right; i++)  // 前半轮,将最大元素放到后面
        if (A[i] > A[i + 1]) 
        {
            exchange(A, i, i + 1);
        }
    right--;
    for (int i = right; i > left; i--)  // 后半轮,将最小元素放到前面
        if (A[i - 1] > A[i]) 
        {
            exchange(A, i - 1, i);
        }
    left++;
}

详细过程
鸡尾酒排序

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的平均时间复杂度为O(n^2)

代码解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0; i < a.length - 1; i++) {
    minIndex = i;//无序区的最小数据数组下标
    for (intj = i + 1; j < a.length; j++) {
        //在无序区中找到最小数据并保存其数组下标
        if (a[j] < a[minIndex]) {
            minIndex = j;
        }
    }
    if (minIndex != i) {
        //如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

详细过程
选择排序
选择排序2