package shanxi.weinan.sfproject;
/**
* 数组
* 为什么数组要从0开始编号，而不是从1开始呢？
* 数组"下标"最确切的定义是"偏移（offset）"，即a[0]就是偏移为0的位置，也就是首地址，a[k]就是偏移k个type_size的位置，则得到下面公示
* a[k]_address = base_address + k * type_size
* 如果下标从1开始，公示为：
* a[k]_address = base_address + (k - 1) * type_size
* 对比两个公示，不难发现，从1开始编号，每次随机访问数组元素都多了一次减法运算，对与CPU就多了一次减法指令。
*
* 还有可能：沿用了从0计数的习惯，减少程序员学习成本。
*
* @author wlw
*/
public class MyArray {
/**
* 数组（Array）：是一种线性表数据结构。它用一组连续的内存空间，来存储具有相同类型的数据。适合查找，不适合增删
* 删除、插入时间复杂度：O(n)；根据下标随机访问的时间复杂度：O(1)。查找操作的时间复杂度(二分查找)：O(logn)
*/
public static void main(String[] args) {
// 冒泡排序
int[] array = {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};
// bubbleSort(array);
// selectionSort(array);
insertSort(array);
for (int i : array) {
System.out.print(i);
System.out.print(" ");
}
}
/**
* 冒泡排序（按从小到大排序）
* 思路：需要两层for循环，第一层是比较的趟数（每一趟都会确定一个最大/最小的数）。
* 第二层是比较的次数（两两数据进行比较，将最小/最大放置最末尾）。
*
* 最好时间复杂度：O(n2)；最坏时间复杂度：O(n2)；平均时间复杂度：O(n2)；
*/
private static void bubbleSort(int[] array) {
// int[] array = {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};
if (null == array || array.length < 2) {
return;
}
for (int i = 0; i < array.length -1; i++) {
// 减 1 的操作是为了防止在 j + 1 时数组越界导致的异常；
// 减 i 是因为已经有i+1位的数据已经按顺序排好了，避免重复排序
for (int j = 0; j < array.length - 1 - i; j++) {
int temp = array[j + 1];
if (array[j + 1] < array[j]) {
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
/**
* 选择排序（按从小到大排序）
* 思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，
* 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
*
* 最好时间复杂度：O(n2)；最坏时间复杂度：O(n2)；平均时间复杂度：O(n2)；
*/
private static void selectionSort(int[] array) {
// int[] array = {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};
if (null == array || array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
// 最小数的下标
int minIndex = i;
// 从数组中找到最小的数的下标。j = i是为了避免将一排好序数据再次进行比较，减少比较次数。
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 将目标与找到的最小数进行交换
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
/**
* 插入排序（按从小到大排序）
* 思路：类似玩扑克牌是，将乱序的牌排列成正序/反序。
* （将目标数据与前者一一比较，较大的数据依次完后挪位置，直到遇到较小的数据为止，此时，较小位置右侧会有一个空位，用于放入目标数）
* 假如要排序的数组{4, 3, 2, 1} 中有4个元素，
* 每轮指定一个要插入的数据（index = i）和改数据的前一位的下标（leftIndex = i - 1）
*
* 第一轮，先取出要插入的数据，取出第二个元素3，与4比较后，较小则将4放到3位置上，此时leftIndex-- == 0内嵌循环结束，
* 再将3放入4位置。此时数组为 {3, 4, 2, 1}
*
* 第二轮，先取出要插入的数据，取出第三个元素2，与4比较后，较小则将4放到2位置上，此时leftIndex-- == 1内嵌循环继续，
* 再次执行内嵌循环，将2与3比较，较小则将3放到原有4的位置上，此时leftIndex-- == 0内嵌循环结束，
* 3的位置将被空出来，用于放入2。此时数组为 {2, 3, 4, 1}
*
* 第三轮，先取出要插入的数据，取出第四个元素1，与4比较后，较小则将4放到1位置上，此时leftIndex-- == 2内嵌循环继续，
* 再次执行内嵌循环，将1与3比较，较小则将3放到原先4位置上，此时leftIndex-- == 1内嵌循环继续，
* 再次执行内嵌循环，将1与2比较，较小则将2放到原先3位置上，此时leftIndex-- == 0内嵌循环继续，
* 2的位置将被空出来，用于放入1。此时数组为 {1, 2, 3, 4}
*
* 最好时间复杂度：O(n)；最坏时间复杂度：O(n2)；平均时间复杂度：O(n2)；
*/
private static void insertSort(int[] array) {
// int[] array = {3, 4, 6, 1, 8, 2, 1, 5, 9, 0};
if (null == array || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
// 用作比较的数据（也就是要插入的牌）
int temp = array[i];
int leftIndex = i - 1;
// 查到要插入的合适位置
while (leftIndex >= 0 && array[leftIndex] > temp) {
// 该处的leftIndex + 1 和 下面的 leftIndex + 1 不是一回事。
// 该处 leftIndex + 1 是为目标数据腾位置。
array[leftIndex + 1] = array[leftIndex];
leftIndex--;
}
// 该处的leftIndex + 1 和上面的 leftIndex + 1 不是一回事
// 该处leftIndex + 1 是 最终找到的要插入的合适位置。
array[leftIndex + 1] = temp;
}
}
/**
* 希尔排序
*/
/**
* 归并排序
*/
/**
* 快速排序
*/
/**
* 堆排序
*/
/**
* 计数排序
*/
/**
* 桶排序
*/
/**
* 递归 递归算法计算n!
*/
/**
* 递归 递归计算1*2+2*3+3*4+...+n*(n+1)
*/
}
常见数组排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
