经常被问到-今天讲解下排序算法七大步，Android自学资料

             numbers[j] = numbers[j + 1]; 
            numbers[j + 1] = temp; 
            flag = true; 
         } 
     }
 }

}


#### 二丶选择排序算法
##### 基本思想：
 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数 当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比 较为止。

**Java 实现**

public static void selectSort(int[] numbers) {
int size = numbers.length; // 数组长度
int temp = 0; // 中间变量
for (int i = 0; i < size-1; i++) {
int k = i; // 待确定的位置
// 选择出应该在第i个位置的数
for (int j = size – 1; j > i; j–) {
if (numbers[j] < numbers[k]) {
k = j;
}
}
// 交换两个数
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}

时间复杂度O(n*n) 性能上优于冒泡排序 交换次数少
#### 三丶插入排序算法
##### 基本思想： 
每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位 置（从后向前找到合适位置后），直到全部插入排序完为止。
**Java 实现**

public static void insertSort(int[] numbers) {
int size = numbers.length;
int temp = 0;
int j = 0;
for (int i = 1; i < size; i++) {
temp = numbers[i];
// 假如temp比前面的值小，则将前面的值后移
for (j = i; j > 0 && temp < numbers[j – 1]; j–) {
numbers[j] = numbers[j – 1];
}
numbers[j] = temp;
}
}

时间复杂度 
O(n*n) 性能上优于冒泡排序和选择排序

#### 四丶希尔排序算法 
##### 基本思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序 列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
**Java 实现**

/**

希尔排序的原理:根据需求，如果你想要结果从小到大排列，它会首先将数组进行分组，然后将较小值移到前面，较大值
移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，
可以说希尔排序是加强版的插入排序拿数组5, 2,8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
此例子是按照从小到大排列，所以小的会排在前面，第一次排序后数组为5, 1, 3, 4, 2, 8，9
第一次后increment的值变为3/2=1,此时对数组进行插入排序，实现数组从大到小排
*/
public static void shellSort(int[] data) {
int j = 0;
int temp = 0;
// 每次将步长缩短为原来的一半
for (int increment = data.length / 2; increment > 0; increme nt /= 2) {
for (int i = increment; i < data.length; i++) {
temp = data[i];
for (j = i; j >= increment; j -= increment) {
if (temp < data[j – increment])// 从小到大排
{
data[j] = data[j – increment];
} else {
break;
}
}
data[j] = temp;
}
}
```
#### 五丶堆排序算法
##### 基本思想:
堆排序是一种树形选择排序，是对直接选择排序的有效改进。 
```

堆的定义下： 具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=h2i+1） (i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。

思想: 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

Java 实现

   public static void heapSort(int[] a){ 
      int arrayLength = a.length; 
      // 循环建堆 
      for (int i = 0; i < arrayLength - 1; i++) { 
          // 建堆 
          buildMaxHeap(a, arrayLength - 1 - i); 
         // 交换堆顶和最后一个元素 
         swap(a, 0, arrayLength - 1 - i); 
         System.out.println(Arrays.toString(a)); 
      }
   }
   // 对data数组从0到lastIndex建大顶堆 
   public static void buildMaxHeap(int[] data, int lastIndex) { 
      // 从lastIndex处节点（最后一个节点）的父节点开始 
     for (int i = (lastIndex - 1) / 2; i >= 0; i--) { 
          // k保存正在判断的节点 
          int k = i; 
         // 如果当前k节点的子节点存在 
         while (k * 2 + 1 <= lastIndex) {
         // k节点的左子节点的索引 
         int biggerIndex = 2 * k + 1; 
        // 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k 节点的右子节点存在
         if (biggerIndex < lastIndex) { 
            // 若果右子节点的值较大 
            if (data[biggerIndex] < data[biggerIndex + 1]) { 
               // biggerIndex总是记录较大子节点的索引 
               biggerIndex++; 
           } 
         }
         // 如果k节点的值小于其较大的子节点的值 
         if (data[k] < data[biggerIndex]) { 
              // 交换他们 
              swap(data, k, biggerIndex); 
              // 将biggerIndex赋予k，开始while循环的下一次循环，重新 保证k节点的值大于其左右子节点的值 
              k = biggerIndex; 
         } else { 
              break; 
         } 
       } 
     } 
   }
   // 交换 
   private static void swap(int[] data, int i, int j) { 
      int tmp = data[i]; 
      data[i] = data[j]; 
      data[j] = tmp; 
  }

六丶快速排序算法

基本思想：

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
Java 实现


  /**
   * 快速排序 
   *
   * @param numbers 
   * 带排序数组 
   */ 
   public static void quick(int[] numbers) { 
      if (numbers.length > 0) // 查看数组是否为空 
      { 
         quickSort(numbers, 0, numbers.length - 1); 
      } 
  }
  /**
   *
   * @param numbers 
   * 带排序数组 
   * @param low 
   * 开始位置 
   * @param high 
   * 结束位置 
   */ 
    public static void quickSort(int[] numbers, int low, int high) { 
        if (low >= high) { 
            return; 
        }
        int middle = getMiddle(numbers, low, high); // 将numbers数组 进行一分为二 
        quickSort(numbers, low, middle - 1); // 对低字段表进行递归排序 
        quickSort(numbers, middle + 1, high); // 对高字段表进行递归排序 
  }
  /**
### 尾声

面试成功其实都是必然发生的事情，因为在此之前我做足了充分的准备工作，不单单是纯粹的刷题，更多的还会去刷一些Android核心架构进阶知识点，**比如：JVM、高并发、多线程、缓存、热修复设计、插件化框架解读、组件化框架设计、图片加载框架、网络、设计模式、设计思想与代码质量优化、程序性能优化、开发效率优化、设计模式、负载均衡、算法、数据结构、高级UI晋升、Framework内核解析、Android组件内核等。**
![](https://s2.51cto.com/images/20210909/1631124741252711.jpg)

不仅有学习文档，视频+笔记提高学习效率，还能稳固你的知识，形成良好的系统的知识体系。这里，笔者分享一份从架构哲学的层面来剖析的视频及资料分享给大家梳理了多年的架构经验，筹备近6个月最新录制的，相信这份视频能给你带来不一样的启发、收获。

![](https://s2.51cto.com/images/20210909/1631124742943072.jpg)

##### Android进阶学习资料库

一共十个专题，包括了Android进阶所有学习资料，Android进阶视频，Flutter，java基础，kotlin，NDK模块，计算机网络，数据结构与算法，微信小程序，面试题解析，framework源码！

![image](https://s2.51cto.com/images/20210909/1631124742683799.jpg)

##### 大厂面试真题

PS：之前因为秋招收集的二十套一二线互联网公司Android面试真题 （含BAT、小米、华为、美团、滴滴）和我自己整理Android复习笔记（包含Android基础知识点、Android扩展知识点、Android源码解析、设计模式汇总、Gradle知识点、常见算法题汇总。）

![](https://s2.51cto.com/images/20210909/1631124742712237.jpg)

**《2017-2021字节跳动Android面试历年真题解析》**

![](https://s2.51cto.com/images/20210909/1631124742512010.jpg)

如果需要PDF版本可以自行领取！

* ##### **[点击这里直达下载领取链接](https://gitee.com/vip204888/android-p7)**

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/147232.html

经常被问到-今天讲解下排序算法七大步，Android自学资料

六丶快速排序算法

基本思想：

相关推荐

发表回复