php+mysql网站开发全程实例 于荷云 pdf/百度总部地址

Android开发中的数据结构与算法：排序算法

在Android开发中，排序算法是我们经常需要用到的基础算法。无论是对用户数据进行排序展示，还是在后台进行数据处理，掌握常见的排序算法及其性能特点都是非常必要的。本文将深入讲解常见排序算法的原理、实现以及在Android开发中的应用场景。

一、常见排序算法概述

排序算法可以根据时间复杂度分为O(n²)、O(nlogn)和O(n)三类。下面我们将介绍几种常见的排序算法。

1.1 时间复杂度为O(n²)的排序算法

1.1.1 冒泡排序

冒泡排序是最简单的排序算法之一，它通过重复遍历要排序的数列，一次比较两个元素，如果顺序错误就交换它们。

public void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换arr[j]和arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

优化版冒泡排序，当某次遍历没有发生交换时，说明数组已经有序，可以提前结束：

public void optimizedBubbleSort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果没有发生交换，则数组已经有序if (!swapped) {break;}}
}

1.1.2 选择排序

选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序数据中选出最小（或最大）的元素，放在已排序序列的末尾。

public void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换arr[i]和arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}

1.1.3 插入排序

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 将比key大的元素向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}

1.2 时间复杂度为O(nlogn)的排序算法

1.2.1 快速排序

快速排序是一种分治算法，它通过选择一个"基准"元素，将数组分为两部分，一部分小于基准，另一部分大于基准，然后递归地对两部分进行排序。

public void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}
}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;// 交换arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交换arr[i+1]和arr[high]（基准）int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}

1.2.2 归并排序

归并排序也是一种分治算法，它将数组分成两半，递归地对它们进行排序，然后将两个有序数组合并成一个有序数组。

public void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}private void merge(int[] arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int[] L = new int[n1];int[] R = new int[n2];for (int i = 0; i < n1; i++) {L[i] = arr[left + i];}for (int j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}

1.2.3 堆排序

堆排序利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

public void heapSort(int[] arr) {int n = arr.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 一个个从堆顶取出元素for (int i = n - 1; i > 0; i--) {// 将当前最大元素移到末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 对剩余元素重新堆化heapify(arr, i, 0);}
}private void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}
}

1.3 时间复杂度为O(n)的排序算法

1.3.1 计数排序

计数排序是一种非比较排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为O(n+k)，其中k是整数的范围。

public void countingSort(int[] arr) {int n = arr.length;// 找出数组中的最大值int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}// 创建计数数组int[] count = new int[max + 1];// 统计每个元素出现的次数for (int i = 0; i < n; i++) {count[arr[i]]++;}// 重建排序后的数组int index = 0;for (int i = 0; i <= max; i++) {while (count[i] > 0) {arr[index++] = i;count[i]--;}}
}

1.3.2 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

public void radixSort(int[] arr) {if (arr == null || arr.length < 2) return;// 找出最大值int max = arr[0];for (int i = 1; i < arr.length; i++) {max = Math.max(max, arr[i]);}// 对每一位进行计数排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}
}private void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10]; // 0-9的计数器// 统计每个数字出现的次数for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}// 计算每个数字的结束位置for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 构建输出数组for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 复制回原数组System.arraycopy(output, 0, arr, 0, n);
}

1.3.3 桶排序

桶排序是将数据分到有限数量的桶中，每个桶再分别排序的算法。

public void bucketSort(float[] arr) {if (arr == null || arr.length < 2) return;int n = arr.length;// 创建桶List<Float>[] buckets = new ArrayList[n];for (int i = 0; i < n; i++) {buckets[i] = new ArrayList<>();}// 将数据分配到桶中for (float item : arr) {int bucketIndex = (int) (n * item);buckets[bucketIndex].add(item);}// 对每个桶内部进行排序for (List<Float> bucket : buckets) {Collections.sort(bucket);}// 合并所有桶的数据int index = 0;for (List<Float> bucket : buckets) {for (float item : bucket) {arr[index++] = item;}}
}

二、排序算法的性能比较

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(logn)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定

三、Android中的排序应用

3.1 RecyclerView列表排序

在Android开发中，我们经常需要对RecyclerView中的数据进行排序。以下是一个示例：

public class ProductListAdapter extends RecyclerView.Adapter<ProductViewHolder> {private List<Product> products;public void sortByPrice() {// 使用Collections.sort方法，底层是归并排序或TimSortCollections.sort(products, (p1, p2) -> Double.compare(p1.getPrice(), p2.getPrice()));notifyDataSetChanged();}public void sortByName() {Collections.sort(products, (p1, p2) -> p1.getName().compareTo(p2.getName()));notifyDataSetChanged();}public void sortByRating() {Collections.sort(products, (p1, p2) -> Float.compare(p2.getRating(), p1.getRating()));notifyDataSetChanged();}
}

3.2 搜索结果相关性排序

在搜索功能中，我们通常需要根据相关性对结果进行排序：

public class SearchEngine {private List<Product> allProducts;public List<Product> search(String query) {List<Product> results = new ArrayList<>();// 筛选包含查询词的产品for (Product product : allProducts) {if (product.getName().toLowerCase().contains(query.toLowerCase()) ||product.getDescription().toLowerCase().contains(query.toLowerCase())) {results.add(product);}}// 根据相关性进行排序Collections.sort(results, (p1, p2) -> {// 计算相关性得分int score1 = calculateRelevanceScore(p1, query);int score2 = calculateRelevanceScore(p2, query);return Integer.compare(score2, score1); // 降序排序});return results;}private int calculateRelevanceScore(Product product, String query) {int score = 0;String lowerQuery = query.toLowerCase();// 标题匹配权重更高if (product.getName().toLowerCase().contains(lowerQuery)) {score += 10;}// 描述匹配if (product.getDescription().toLowerCase().contains(lowerQuery)) {score += 5;}// 可以添加更多相关性计算规则// 例如：评分权重score += product.getRating() * 2;return score;}
}

四、排序算法面试题解析

4.1 如何选择合适的排序算法？

在实际开发中，选择合适的排序算法需要考虑以下因素：

1. 数据规模：

   • 小规模数据（n < 50）：插入排序
   • 中等规模：快速排序
   • 大规模数据：归并排序或堆排序

2. 数据特征：

   • 接近有序：插入排序
   • 数据范围集中：计数排序或桶排序
   • 整数数据：基数排序

3. 稳定性要求：

   • 需要稳定排序：归并排序、插入排序
   • 不要求稳定：快速排序、堆排序

4. 空间复杂度要求：

   • 要求O(1)：堆排序
   • 可接受O(n)：归并排序

4.2 快速排序的优化策略

1. 三数取中选择基准值：

private int medianOfThree(int[] arr, int left, int right) {int mid = left + (right - left) / 2;if (arr[left] > arr[mid]) swap(arr, left, mid);if (arr[left] > arr[right]) swap(arr, left, right);if (arr[mid] > arr[right]) swap(arr, mid, right);return arr[mid];
}

2. 小规模数据使用插入排序：

public void quickSort(int[] arr, int left, int right) {if (right - left <= 10) {insertionSort(arr, left, right);return;}// 继续快速排序
}

五、总结

1. 排序算法的选择需要根据具体场景：

   • 追求稳定性：选择归并排序
   • 追求效率：选择快速排序
   • 空间受限：选择堆排序
   • 数据范围小：选择计数排序

2. 在Android开发中的应用：

   • 列表数据排序优先使用系统API（Collections.sort）
   • 自定义排序需求时，根据数据特征选择合适算法
   • 注意排序操作的性能影响，考虑异步处理

3. 实际开发建议：

   • 优先使用语言或框架提供的排序工具
   • 需要自定义排序时，优先考虑快速排序
   • 关注排序算法的稳定性需求
   • 注意性能优化，避免主线程大量排序操作