JAVA 算法
- 1.1. 二分查找
- 1.2. 冒泡排序算法
- 1.3. 插入排序算法
- 1.4. 快速排序算法
- 希尔排序算法
- 1.1. 归并排序算法
- 1.2. 桶排序算法
- 1.3. 基数排序算法
- 算法( 二 ):补充
1.1. 二分查找
又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。直到查找到了为止,否则序列中没有待查的关键字。
public static int biSearch(int []array,int a){
int lo=0;
int hi=array.length-1;
int mid;
while(lo<=hi){
mid=(lo+hi)/2;
if(array[mid]==a){
return mid+1;
}else if(array[mid]<a){
lo=mid+1;
}else{
hi=mid-1;
}
}
return -1;
}
1.2. 冒泡排序算法
(1)比较前后相邻的二个数据,如果前面数据大于后面的数据,就将这二个数据交换。
(2)这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1 个位置。
(3)N=N-1,如果 N 不为 0 就重复前面二步,否则排序完成。
public static void bubbleSort1(int[] a, int n) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 1; j < n - i; j++) {
if (a[j - 1] > a[j]) {
int temp;
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
1.3. 插入排序算法
通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入。
插入排序非常类似于整扑克牌。在开始摸牌时,左手是空的,牌面朝下放在桌上。接着,一次从桌上摸起一张牌,并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置,要将它与手中已有的牌从右到左地进行比较。无论什么时候,左手中的牌都是排好序的。
如果输入数组已经是排好序的话,插入排序出现最佳情况,其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的,将出现最坏情况。平均情况与最坏情况一样,其时间代价是(n2)。
public void sort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
int index = i - 1;
while (index >= 0 && insertVal < arr[index]) {
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = insertVal;
}
}
1.4. 快速排序算法
快速排序的原理:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。
一次循环:从后往前比较
,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较
,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引
,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。
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);
if (end < high) sort(a, end + 1, high);
}
}
希尔排序算法
基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
- 操作方法:
选择一个增量序列 t1,t2,…,tk,其中 ti>tj,tk=1; - 按增量序列个数 k,对序列进行 k 趟排序;
- 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
private void shellSort(int[] a) {
int dk = a.length / 2;
while (dk >= 1) {
ShellInsertSort(a, dk);
dk = dk / 2;
}
}
private void ShellInsertSort(int[] a, int dk) {
for (int i = dk; i < a.length; i++) {
if (a[i] < a[i - dk]) {
int j;
int x = a[i];
a[i] = a[i - dk];
for (j = i - dk; j >= 0 && x < a[j]; j = j - dk) {
a[j + dk] = a[j];
}
a[j + dk] = x;
}
}
}
1.1. 归并排序算法
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
public class MergeSortTest {
public static void main(String[] args) {
int[] data = new int[]{5, 3, 6, 2, 1, 9, 4, 8, 7};
print(data);
mergeSort(data);
System.out.println("排序后的数组:");
print(data);
}
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
int center = (left + right) / 2;
sort(data, left, center);
sort(data, center + 1, right);
merge(data, left, center, right);
print(data);
}
public static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right) {
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}
1.2. 桶排序算法
桶排序的基本思想是: 把数组 arr 划分为 n 个大小相同子区间(桶),每个子区间各自排序,最后合并 。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值 max、最小值 min
2.我们使用 动态数组 ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1
3.遍历数组 arr,计算每个元素 arr[i] 放的桶
4.每个桶各自排序
public static void bucketSort(int[] arr) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
}
1.3. 基数排序算法
将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
public class radixSort {
int a[]=
{
49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 101, 56, 17, 18, 23, 34, 15, 35, 2
5, 53, 51
}
;
public radixSort() {
sort(a);
for (inti = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public void sort(int[] array) {
int max = array[0];
for (inti = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int time = 0;
while (max > 0) {
max /= 10;
time++;
}
List<ArrayList> queue = newArrayList < ArrayList > ();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
for (int i = 0; i < time; i++) {
for (intj = 0; j < array.length; j++) {
int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count = 0;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue3 = queue.get(k);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}
算法( 二 ):补充
JAVA 核心知识点篇之算法( 二 ):补充
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)