Bubble sorting and encountering a problem about arrays with one size and one size

Bubble sort

Bubble Sort is a relatively simple sorting algorithm in the field of computer science.

The bubble sort algorithm operates as follows: (from back to front)

1. Compare adjacent elements. If the first one is bigger than the second one, swap them both.
2. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.
3. Repeat the above steps for all elements except the last one.
4. Continue repeating the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

l Compare two adjacent elements in turn and eliminate the reverse order (reverse order is a mathematical concept and appears in pairs. For example, 50 and 30 are a pair of reverse order. The so-called elimination of reverse order means that the larger one is placed behind and the smaller one is placed later. front)

l In this way, after a round of comparison, the pair with the largest number is at the end!

l Then, continue a new round of comparison. Note that the maximum value after the previous round will no longer participate in the comparison. In this way, the values ​​participating in the comparison in this round will be one less than the previous round, and so on Repeat until there are only two values ​​left to compare!

So it is a double loop, the outer layer controls the number of rounds, and the inner layer controls the number of comparisons in each round.

If the array has n elements, a total of n-1 rounds of comparisons are required, which is the number of outer loops!

Add another knowledge point:

list — assign the values ​​​​in the array to some variables, from small to large, and in turn assign the values ​​​​from large to small

Let me talk about the bubble sort I wrote and annotate my own understanding of it:

<span style="color: #008000;">//</span><span style="color: #008000;">冒泡排序，让数组从小到大依次排序</span>
<span style="color: #000000;">function maopao($arr){
    </span><span style="color: #008000;">//</span><span style="color: #008000;">双层循环，外层控制，$i代表循环的轮数，比较轮数等于数组的个数减1,$i<$len相当于数组个数-1，例如8个，当$i=7是最后的比较，符合8-1=7；</span>
    <span style="color: #0000ff;">for</span>($i=<span style="color: #800080;">1</span>,$len=count($arr);$i<$len;$i++<span style="color: #000000;">){
        </span><span style="color: #008000;">//</span><span style="color: #008000;">内层控制每一轮比较的次数，$k=下标，每一轮比较完最后一个将不再参与比较,下标从0开始</span>
        <span style="color: #0000ff;">for</span>($k=<span style="color: #800080;">0</span>;$k<$len-$i;$k++<span style="color: #000000;">){
            </span><span style="color: #008000;">//</span><span style="color: #008000;">比较相邻的两个数，如果前面的数值比后面的大就调换下位置，通过中间数，如果不比它大，则不用调换</span>
            <span style="color: #0000ff;">if</span>($arr[$k]>$arr[$k+<span style="color: #800080;">1</span><span style="color: #000000;">]){
                </span><span style="color: #008000;">//</span><span style="color: #008000;">调换位置</span>
                $tem=<span style="color: #000000;">$arr[$k];
                $arr[$k]</span>=$arr[$k+<span style="color: #800080;">1</span><span style="color: #000000;">];
                $arr[$k</span>+<span style="color: #800080;">1</span>]=<span style="color: #000000;">$tem;
            }
        }
    }
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> $arr;
}
$arr1</span>=array(<span style="color: #800080;">45</span>,<span style="color: #800080;">85</span>,<span style="color: #800080;">12</span>,<span style="color: #800080;">22</span>,<span style="color: #800080;">36</span>,<span style="color: #800080;">7</span>,<span style="color: #800080;">75</span>,<span style="color: #800080;">15</span>,<span style="color: #800080;">40</span>,<span style="color: #800080;">64</span><span style="color: #000000;">);
</span><span style="color: #008000;">//</span><span style="color: #008000;"> echo count($arr1);</span>
echo <span style="color: #800000;">'</span><span style="color: #800000;"><pre class="brush:php;toolbar:false"></span><span style="color: #800000;">'</span><span style="color: #000000;">;
print_r(maopao($arr1));</span></span>

Effect:Achieved sorting of arrays from small to large

If you want to implement from large to small, it is the same algorithm, all are exchanged through comparison of intermediate numbers.

Next, let’s talk about a problem I encountered in an interview: Take an array and let the first one be the largest, the second one be the smallest, the third one be the second largest, and the fourth one be the second smallest... proceed like this Sort.

At that time, I only thought that there seemed to be one

array_pop: Pop the last data of the array

array_shift: Pop data from the front of the array

After sorting the array from large to small, pop out the first one and get the largest one, pop up the last one and get the smallest one, put these two together to get the largest one and the smallest one, and then continue to take out like this until Take them all.

I will try to see if this is feasible when I get back. Now I will talk about the method I tried myself

Example:

SoThe first step: I first sort the array from large to small through bubbling

The second step, I put the first (largest) and last (smallest) pop-up together through recursion, and then take them out until they are all taken out.

Effect:

There is a better way to do this. What I am talking about here is the method that happened to come to my mind at the time. Ha, don’t be offended, just feel free to complain.