package other;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int b = -100000;
System.out.println("b的源码是:"+Integer.toBinaryString(b));
Random r = new Random();
Main m = new Main();
int[] a = new int[100];
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100) + 1; // 生成[1,100]的整数
}
long time1 = System.currentTimeMillis();
m.bubbleSort(a); //冒泡排序
long time2 = System.currentTimeMillis();
System.out.println("冒泡排序"+(time2 - time1) + "ms");
System.out.println("冒泡排序后:数组a中元素:");
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
//矩阵乘法
public void Multiply(int[][] A, int[][] B) { // 矩阵A和B进行相乘
int[][] C;
if (A[0].length != B.length) {
System.out.println("不能进行矩阵相乘运算");
}
C = new int[A.length][B[0].length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B[0].length; j++)
for (int k = 0; k < A[0].length; k++) {
C[i][j] = A[i][k] * B[k][j] + C[i][j];
}
}
}
//-----------------------快速排序begin---------------------------------//
public void quickSort(int[] array, int p, int r) {// 快速排序,使数组array从p到r变成有序的
// 分治策略
if (p < r) {
int q = partion(array, p, r); // 分割成两部分,其中一部分的所有元素小于另一部分中的所有元素,q是中间位置
// 分别对于两部分进行快速排序
quickSort(array, p, q - 1);
quickSort(array, q + 1, r); // 递归调用
}
}
private int partion(int[] array, int p, int r) { // 就是对array进行原地排序,
int x = array[r];
int i = p - 1;
int temp;
for (int j = p; j <= r - 1; j++) { // j指向当前的待排序元素
if (array[j] < x || array[j] == x) {
i++;// i指向小于x的部分的最后一个数
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
temp = array[i + 1];
array[r] = temp;
array[i + 1] = x; // 将中轴换到两个部分的中间位置
return i + 1; // 中轴的位置,中轴左侧都是小于等于中轴值,中轴右侧部分都大于中轴值
}
//-----------------------快速排序end---------------------------------//
//-----------------------选择排序begin---------------------------------//
public void selectionSort(int[] array) { // 选择排序
int j;
int temp = 0;
int min = 0;
for (int i = 0; i < array.length - 1; i++) { //注意这个边界是array.length-1,因为如果前面n-1个有序了,最后一个肯定是最大的
min = i;
for (j = i+1 ; j <= array.length - 1; j++) {
if (array[min] > array[j])
min = j;
}
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
//-----------------------选择排序end---------------------------------//
//-----------------------归并排序begin---------------------------------//
public void mergeSort(int[] a, int p, int r) { // 归并排序,从数组a的p位置到r位置排序
int q;
if (p < r) {
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
merge(a, p, q, r);// 将已经有序的a[p...q]和a[q+1...r]归并成一个有序的a[p...r]
}
}
private void merge(int[] a, int p, int q, int r) { //归并两个有序序列a[p...q]和a[q+1...r]成为有序的a[p...r]
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1]; //辅助数组
int[] R = new int[n2];//辅助数组
for (int i = 0; i < n1; i++) {
L[i] = a[i + p];
}
for (int i = 0; i < n2; i++) {
R[i] = a[i + q + 1];
}
int i = 0, j = 0;// 分别指向L和R两个数组中元素的指针
int k = p; // 指向结果数组元素的指针
while (i < n1 && j < n2) {
if (L[i] <= R[j]) { //两个有序数组的元素进行比较,谁小就加入到结果数组中,并将指针往前移一步
a[k] = L[i];
i++;
k++;
} else {
a[k] = R[j];
j++;
k++;
}
}
if (i < n1) {//while条件不满足了,肯定是 j=n2了,R先插入完,
while (i < n1) {
a[k] = L[i];
k++;
i++;
}
}
if (j < n2) { //while条件不满足了,肯定是 i=n2了,L先插入完
while (j < n2) {
a[k] = R[j];
k++;
j++;
}
}
}
//-----------------------归并排序end---------------------------------//
//-----------------------插入排序begin---------------------------------//
public void insertSort(int[] a){
int i,j,key;
for(i=1;i<a.length;i++){
j=i-1; //有序列的最后一个元素下标
key = a[i];//当前待插入的元素
//将当前元素插入到已经排好序的a[0...i-1]中
while(key<a[j]&&j>0){
a[j+1]=a[j]; //将元素往后移
j--;
}
a[j+1] = key; //插入当前元素
}
}
//-----------------------插入排序end---------------------------------//
//-----------------------冒泡排序begin---------------------------------//
public void bubbleSort(int[] a){
int temp;
for(int i=0;i<a.length;i++){
for(int j=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){ //逆序时,交互相邻两个元素
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
//-----------------------冒泡排序end---------------------------------//
}
分享到:
评论