线性数据结构算法

桃扇骨 2023-07-03 07:11 66阅读 0赞

** [数据][Link 1]结构**是[计算机][Link 2]存储、组织[数据][Link 3]的方式。数据结构是指相互之间存在一种或多种特定关系的[数据元素][Link 4]的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储[效率][Link 5]。数据结构往往同高效的检索[算法][Link 6]和[索引][Link 7]技术有关。

图形结构                                                       树形结构                                           线性结构                                集合结构

![20200203233735516.png][]

1.冒泡排序

在进行冒泡法排序（升序）时，将第一个数与后继的数进行比较，如果顺序则继续第二个数与后继的数进行比较；如果逆序则交换位置，继续和后继的数进行比较，完成第一趟冒泡排序。同理，直到数组有序。

如果经过一趟冒泡排序不发生数据交换说明数组原本有序。

最好时间复杂度：O(n)

平均时间复杂度：O(n^2)

最坏时间复杂度： O(n^2)

空间复杂度： O(1)

代码示例

/**
         * 冒泡排序
         *
         * @param array
         * @return 相邻数据对比，交互位置
         */
        public static int[] bubblingSort(int[] array) {
            //从后一位开始循环对比，直到循环完。
            for (int i = array.length - 1; i > 0; i--) {
                boolean flag = true;
                //把最大的筛选到最后
                for (int j = 0; j < array.length - 1; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                        flag = false;
                    }
                }
                //优化减少循环的次数
                if (flag) {
                    break;
                }
            }
            return array;
        }
    
    
         public static void main(String[] args) {
                int[] array = new int[]{3, 2, 5, 8, 1, 9, 4, 6, 7};
                bubblingSort(array);
                for (int i : array) {
                    System.out.print(i + " ");
                }
            }

排序结果:

第1次排序:\[2,3,5,1,8,4,6,7,9\]  
第2次排序:\[2,3,1,5,4,6,7,8,9\]  
第3次排序:\[2,1,3,4,5,6,7,8,9\]  
第4次排序:\[1,2,3,4,5,6,7,8,9\]  
第5次排序:\[1,2,3,4,5,6,7,8,9\]  
1 2 3 4 5 6 7 8 9

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70][]

2、 选择排序：把第一个数与他后面的数进行比较，如果顺序则继续与后面比较，如果逆序则两数交换位置，继续将第一个数与交换位置后的数进行比较，这样就完成了第一轮排序。同理将第二位与其后的数比较，直到数组有序为止。

最好时间复杂度：O(n)

平均时间复杂度：O(n^2)

最坏时间复杂度： O(n^2)

空间复杂度：O(1)

代码示例

/***
         * 选择排序
         * @param array
         * @return
         *
         */
        public static int[] selectSort(int[] array) {
            for (int i = 0; i <array.length-1 ; i++) {
                int index = i;
                for (int j = i+1; j < array.length ; j++) {
                    if (array[j] < array[index]) {
                        index =j;//如果有一个小于固定位置的数，就对换位置。
                    }
                }
                //如果已经是最小的，就不需要交换
                if(index!=i){
                    int temp =array[index];
                    array[index] =array[i];
                    array[i] = temp;
                }
            }
            return array;
        }
    
         public static void main(String[] args) {
                int[] array = new int[]{3, 2, 5, 8, 1, 9, 4, 6, 7};
               selectSort(array);
                for (int i : array) {
                    System.out.print(i + " ");
                }
            }

排序结果：

第0次排序:\[1,2,5,8,3,9,4,6,7\]  
第1次排序:\[1,2,5,8,3,9,4,6,7\]  
第2次排序:\[1,2,3,8,5,9,4,6,7\]  
第3次排序:\[1,2,3,4,5,9,8,6,7\]  
第4次排序:\[1,2,3,4,5,9,8,6,7\]  
第5次排序:\[1,2,3,4,5,6,8,9,7\]  
第6次排序:\[1,2,3,4,5,6,7,9,8\]  
第7次排序:\[1,2,3,4,5,6,7,8,9\]  
1 2 3 4 5 6 7 8 9

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70 1][]

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE/5947370
[Link 2]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA/140338
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE
[Link 4]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 5]: https://baike.baidu.com/item/%E6%95%88%E7%8E%87/868847
[Link 6]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
[Link 7]: https://baike.baidu.com/item/%E7%B4%A2%E5%BC%95/5716853
[20200203233735516.png]: https://img-blog.csdnimg.cn/20200203233735516.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200204105929552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200204105717363.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI=,size_16,color_FFFFFF,t_70