概述
矩阵排序-行列升降序
- 1、描述
- 2、实现步骤
- 2.1 冒泡排序算法
- 2.1.1 思路
- 2.1.2 java代码实现
- 2.2 矩阵排序的实现
- 2.3 测试函数
- 3. 算法分析
- 3.1 冒泡排序算法分析
- 3.2 矩阵排序算法分析
1、描述
将无序矩阵按照从上到下、从左到右进行升序排序或降序排序,使其成为有序矩阵。
2、实现步骤
- 先将矩阵每行进行有序排序,矩阵每行为数组,采取冒泡排序的算法
- 对排序后的矩阵按列进行排序,矩阵每列为数组,采取冒泡排序的算法
2.1 冒泡排序算法
- 原理:比较两个相邻的元素,将值大的元素交换到右边
2.1.1 思路
依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。即:
(1)第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。
(2)比较第2和第3个数,将小数 放在前面,大数放在后面。
…
(3)如此继续,知道比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成。
(4)在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。
(5)在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。
(6)依次类推,每一趟比较次数减少依次
2.1.2 java代码实现
/**
* 冒泡法对数组进行排序
* @param array
* @param isAssecding true:升序 false: 降序
* @return
*/
public void bubblingSortArray(int[] array, boolean isAssecding) {
if(array == null || array.length < 2){
return;
}
//N个数字冒泡排序,总共要进行N-1趟比较,每趟的排序次数为(N-i)次比较
for(int i = 0;i<array.length-1; i++){
//第i趟比较
for(int j = i+1;j < array.length ; j++){
//开始进行比较,如果array[i]比array[j]的值大,那就交换位置
if(isAssecding){
if(array[i] > array[j]){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}else{
if(array[i] < array[j]){
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
}
}
}
2.2 矩阵排序的实现
public class MatrixSorting {
/**
* 创建有序矩阵
* @param row 矩阵行数
* @param col 矩阵列数
* @param min_ele 矩阵元素最小值
* @param max_ele 矩阵元素最大值
* @param isAssecding true:从左到右,从上到下均升序排列; false:从左到右,从上到下均降序排列
* @return
*/
public int[][] createSortMatrix(int row,int col,int min_ele,int max_ele,boolean isAssecding){
int[][] matrix = createOneRandomMatrix(row,col,min_ele,max_ele);
sortMatrix(matrix, isAssecding);
return matrix;
}
/**矩阵的排序:
* isAssecding->true: 从左到右,从上到下都是升序
* isAssecding->false: 从左到右,从上到下都是降序*/
public void sortMatrix(int[][] matrix,boolean isAssecding){
if(matrix == null || matrix.length == 0){
return ;
}
//排序矩阵每行元素
for(int i = 0;i<matrix.length; i++){
bubblingSortArray(matrix[i],isAssecding);
}
//排序矩阵每列元素
int[] col_array = null;
for(int i = 0;i<matrix[0].length; i++){
col_array = new int[matrix.length];
for(int j = 0;j < matrix.length;j++){
col_array[j] = matrix[j][i];
}
bubblingSortArray(col_array,isAssecding);
for(int j = 0;j < matrix.length;j++){
matrix[j][i] = col_array[j];
}
}
}
/**生成元素在min-max数值范围内的随机矩阵M[row]*[col]*/
public int[][] createOneRandomMatrix(int row, int col,int min,int max) {
int[][] matrix = new int[row][col];
for(int i = 0;i<row;i++){
for(int j = 0;j<col;j++){
matrix[i][j] = (int)(Math.random()*(max-min));
}
}
return matrix;
}
/**打印矩阵*/
public void printMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0){
System.out.println("矩阵无元素");
return;
}
for(int i = 0;i<matrix.length;i++){
for(int j = 0;j<matrix[0].length;j++){
System.out.print(getStr(matrix[i][j],4));
}
System.out.println();
}
System.out.println();
}
/**
* 返回数值n的length长度字符串
*/
public String getStr(int n,int length){
int k = 10;
int n_length = 0;
String n_str = "";
while(n/k > 1){
n_length++;
k *= 10;
}
if(n_length >= length){
n_str = n+" ";
}else{
n_str = n+"";
for(int i = length-n_length; i>=0; i--){
n_str += " ";
}
}
return n_str;
}
}
2.3 测试函数
public static void main(String[] args) {
MatrixSorting t = new MatrixSorting();
int[][] matrix = t.createOneRandomMatrix(4,5,0,100);
System.out.println("原始矩阵打印如下:");
t.printMatrix(matrix);
t.sortMatrix(matrix, true);
System.out.println("排序后的矩阵打印如下:");
t.printMatrix(matrix);
}
- 测试升序排序结果:
- 测试降序排序结果:
3. 算法分析
3.1 冒泡排序算法分析
(1)由此可见:N个数字要排序完成,总共进行N-1趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数。
(2)冒泡排序的优点:
每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,没进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。
(3)时间复杂度:
如果我们的数据正序,只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值,即:Cmin=n-1;Mmin=0;所以,冒泡排序最好的时间复杂度为O(n)。
如果很不幸我们的数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
综上所述:冒泡排序总的平均时间复杂度为:O(n*n) ,时间复杂度和数据状况无关。
3.2 矩阵排序算法分析
m行n列矩阵中,行排序为:mO(nn),列排序为:nO(mm)
下一章:有序矩阵的快速查找
最后
以上就是辛勤身影为你收集整理的java-矩阵排序-行列升\降序1、描述2、实现步骤3. 算法分析的全部内容,希望文章能够帮你解决java-矩阵排序-行列升\降序1、描述2、实现步骤3. 算法分析所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复