算法(1)--排序

排序

排序方法

选择排序

选择排序的思路是找到数组中最小的数和第一个元素交换位置，然后在剩下的元素中找到最小的元素和第二个元素交换位置，
直到最后只剩一个元素，这样就是一个从小到大排好序的数组。选择排序的复杂度为O(n^2)。

插入排序

插入排序的思路是将元素插入一个已经排好序的子列表中，直到整个列表都排序完成。插入排序的复杂度为O(n^2)。

冒泡排序

冒泡排序的思路是每次对连续的邻居元素进行比较，两个元素是逆序排序就交换位置，否则保持不变，直到所有元素都被排序好。每次进行完一轮比较，就能将最大或者最小的元素移到其最终的位置上，当不再发生交换的时候，就说明元素已经被排好序了，冒泡排序的复杂度是O(n^2)。

归并排序

归并排序的思路是利用递归的方法，将数组分为两半，各自进行归并排序的过程。其关键是如何将排好序的两个子数组也排好序，鉴于两个子数组是已经排好序了的，只需要将两个子数组依次比较。归并排序的复杂度是O(nlogn）。

快速排序

快速排序的思路是挑出一个中心点，把数组分为两半，其中一半所有元素都小于这个中心点，另一半大于这个中心点，再对这两半进行递归处理，所以快速排序的关键在于这个中心点的选择了。快速排序的复杂度是O(nlogn）。

堆排序

堆排序用了二叉堆，将一个数组中的所有元素添加到堆中，然后将堆中最大的元素连续移除以获得一个排好序的数组。一个二叉堆具有如下性质：是一个完全二叉树；每个节点都大于或等于它的子节点，二叉堆通常是用数组实现的，父母节点和子节点的位置满足一定的关系，假如一个在位置i的节点，它的左子节点就在位置2i+1上，右子节点在位置2i+2上。所以堆排序的关键在于二叉堆的建立和维护。堆排序的复杂度是O(nlogn)。

桶排序和基数排序

桶排序和基数排序用于排序整数非常有效。

• 桶排序

​ 桶排序的思路是加入数组中的元素在0到t的范围内，则把这些元素放入对应的标记上0到t的桶当中，每个桶中的元素值都是相同的。

• 基数排序

  在桶排序中，如果元素范围过大的话，就会需要很多桶，此时就可以用基数排序。基数排序基于桶排序，只是基数排序只会用到十个桶，基于基数位置进行桶排序。

外排序

当数据量大到无法一次性载入内存时，使用外排序。外排序的思路就是将大量数据拆分成小块数据，小块数据进行内排序之后，再分别合并排序。

相关java基础

数组

数组一旦创建了，大小就是固定的。
java中声明数组变量的语法是’elementType[] arrayRefVar;’，声明数组只是创造了一个数组引用的存储位置，并没有为这个数组分配内存，创建一个数组可以使用new操作符，
例如’array RefVar = new elementType[arraySize];’。

• 数组的拷贝
  数组变量是一个数组的引用，直接使用赋值语句只是让两个变量去指向同一个数组（同一片存储空间），要想真正地拷贝数组有几种方式：
  使用循环对数组中的元素一个一个地拷贝；使用System类中的静态方法arraycopy；使用clone方法。
  arraycopy的语法是’arraycopy(sourceArray,srcPos,targetArray,tarPos,length);’。