排序相关的基本概念
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法。
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
内排序:在排序期间数据对象全部放在内存中的排序
外排序:排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内外存中移动排序.
桶排序:适合max很小的情况
1.建议一堆buckets
2.遍历原始数组,并将数据放入到各自的buckets中
3.对非空的buckets进行排序
4.按照顺序遍历这些buckets并返回到原始数组中即可构成排序后的数组.
冒泡排序
import java.util.Random;
public class BubbleSort {
public static void main(String[] args){
Random rand =new Random(5);
int score[]=new int[5];
for(int i=0;i<5;i++)
score[i]=rand.nextInt(100);
for (int i = 0; i < score.length -1; i++){ //最多做n-1趟排序
for(int j = 0 ;j < score.length - i - 1; j++){ //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围是在逐步缩小的)
if(score[j] >score[j + 1]){ //把大的值交换到后面
int temp = score[j];
score[j] = score[j + 1];
score[j + 1] = temp;
}
}
System.out.print("第" + (i + 1) + "次排序结果：");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "\t");
}
System.out.println("");
}
System.out.print("最终排序结果：");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "\t");
}
}
}
归并排序算法思想:
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.
public static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, tmp, left, mid);// 左排序
mergeSort(a, tmp, mid + 1, right);// 右排序
merge(a, tmp, left, mid + 1, right);// 左右合并
}
}
public static void merge(int[] a, int[] tmp, int left, int rightPos,
int right) {
int leftEnd = rightPos - 1;
int tmpPos = left;
int num = right - left + 1;
while (left <= leftEnd && rightPos <= right) {
if (a[left] < a[rightPos]) {
tmp[tmpPos++] = a[left++];
} else {
tmp[tmpPos++] = a[rightPos++];
}
}
while (left <= leftEnd) {
tmp[tmpPos++] = a[left++];
}
while (rightPos <= right) {
tmp[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < num; i++, right--) {
a[right] = tmp[right];
}
}
快速排序:随机选定一个元素作为轴值,利用该轴值将数组分为左右两部分,左边元素都比轴值小,右边元素都比轴值大,但他们不是完全排序的.在此基础上,分别对
左右两部分调用快速排序,使得左右部分完全排序.
public void sort(int[] a,int low,int high){
int start = low;
int end = high;
int key = a[low];
while(end>start){
//从后往前比较
while(end>start&&a[end]>=key) //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//从前往后比较
while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
//递归
if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
}
希尔排序:将无序数组分割为若干子序列,子序列不是逐段分割的,而是相隔特定增量的子序列.对各个子序列进行插入排序,然后再选择一个更小的增量,再将数组分割为
多个子序列进行排序...最后选择增量为1,即使用直接插入排序,使最终数组成为有序.
------------------------------------------------------------------------------------------------------------------------------------------------------
二分查找
public class Efcz {
public static void main(String[] args) {
int[] a={1,2,3,4,5,6,7,8,9};
int value=binary(a,9);
System.out.println(value);
}
public static int binary(int[] array,int value)
{
int low=0;
int high=array.length-1;
while(low<=high){
int middle=low+(high-value)/2;
if(value==array[middle])
return middle;
if(value>array[middle])
low=middle+1;
if(value<array[middle])
high=middle-1;
}
return -1;
}
}
------------------------------------------------------------------------------------
红黑树的五个性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
--------------------------------------------------------------------------------------
入栈数为n,出栈数种类为1/(n+1)*c(2n,n)
--------------------------------------------------------------------------------------------------------------------------------------------------------------
从n个数中找出最小的k个数(n >> k)，最优平均时间复杂度是？
.对前k个数，建立最大堆，对于后面N-k个数，依次和最大堆的最大数比较，如果小于最大数，则替换最大数，并重新建立最大堆。时间复杂度为O(N*logk)。
-------------------------------------------------------------------------------------------------------------------------------------------------------------
广度遍历用队列做辅助，深度遍历用栈做辅助.
----------------------------------------------------------------------------------------------------------------------------------------------
什么是二叉查找树，原理
二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
哈夫曼树
给定n 个权值作为n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二
叉树，也称为哈夫曼树(Huffman tree)。
构造方法：
假设有n 个权值，则构造出的哈夫曼树有n 个叶子结点。n 个权值分别设为w1、w2、…、wn，则
哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn 看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权
值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
京公网安备 11010502036488号