如果下一个元素大于当前值，则交换数组中的元素

Question

如果下一个元素大于当前值，我想要在arr中更改顺序。 热修改代码，所以它会工作？

arr = [5, 22, 29, 39, 19, 51, 78, 96, 84] 
i = 0 
while (i < arr.size-1) 
    if arr[i].to_i < arr[i+1].to_i 
     arr[i] 
    elsif arr[i].to_i > arr[i + 1].to_i 
      arr[i+1], arr[i] = arr[i], arr[i+1] 
    end 
    puts arr[i] 
    i += 1 

end 

返回：[5，第22，29，39，19，51，78，96，84] 相反：[5，19，22，29，39，51，78，84，96]

Answer 1

可以使用任何的不同阵列（n）的大小的排序算法，

For Bubble Sort, Time Complexity is O(n^2) 
For Merge Sort, Time Complexity is O(nlogn) 
For Counting Sort, Time Complexity is O(n) but number in array must be 0.upto 10^6 

冒泡排序：它运行成对在一次迭代中，把最大元素在最后，在第二次迭代中，将第二个最大元素放在倒数第二个位置，依此类推直到数组排序。

1. 迭代（N-1）次〔找到第（n-1）max的数字]

2. 迭代（N-IDX-1）倍来交换数字对如果（第一个数字是 大于下一个号码）

3. 如果内环交换停止意味着阵列变得排序， 所以打破外环

ř uby代码：

def bubble_sort(arr) 
     n = arr.size 
     (n-1).times do |idx| 
     swapped = false 
     (n-idx-1).times do |i| 
      if arr[i] > arr[i+1] 
      arr[i], arr[i+1] = arr[i+1], arr[i] 
      swapped = true 
      end 
     end 
     break unless swapped 
     end 
     arr 
end 

p bubble_sort([5, 22, 29, 39, 19, 51, 78, 96, 84]) 

归并排序：它，如果你知道数组的两半的排序，那么你可以通过使用O（N）two pointer战略梳理整个阵列上运行divide and conquer战略，即。

例如，

#first half : [4,5,7,9] 
#second half : [1,2,10,15] 

1. Take two pointer l and r assigned to starting index of both halves i.e 0 
2. Iterate over l and r upto their lengths to consume both arrays 
    if element at first_half[l] < second_half[r] 
     Put first_half[l] in result_array 
     Increment l pointer 
    else 
     Put second_half[r] in result_array 
     Increment r pointer 

此合并操作将需要O（N）进行排序整个阵列。我们将得到高度为log（n）的二叉树，每个级别将用O（n）对子问题进行排序（一半），从而产生O（nlogn）时间复杂性。

Base case would be : single element array is always sorted 

红宝石代码：

def merge(left_sorted, right_sorted) 
    res = [] 
    left_size, right_size = left_sorted.size, right_sorted.size 
    l = r = 0 
    loop do 
    break if r == right_size and l == left_size # break if both halves processed 
    if r == right_size or (l < left_size and left_sorted[l] < right_sorted[r]) 
     res << left_sorted[l]; l += 1 
    else 
     res << right_sorted[r]; r += 1 
    end 
    end 
    res 
end 

def merge_sort(arr) 
    size = arr.size 
    return arr if size <= 1 # base case 
    mid = arr.size/2 - 1 
    left_half, right_half = arr[0..mid], arr[mid+1..-1] 
    left_sorted = merge_sort(left_half) 
    right_sorted = merge_sort(right_half) 
    return merge(left_sorted, right_sorted) 
end 

p merge_sort([5, 22, 29, 39, 19, 51, 78, 96, 84]) 

计数排序：它通过在阵列计数数字外观工作在O（N），如果在数字阵列位于范围（0..10^6）

1. 保持count_array中数组的每个数的个数。从min_element
2. 迭代到max_element阵列的，如果出现了，即其计数把元素 sorted_array> 0

的Ruby代码：

def counting_sort(arr) 
    min, max = arr.min, arr.max 
    count_arr = [0] * (max - min + 1) # initialize count_array with all 0s 
    arr.each do |num| 
    count_arr[num - min] += 1 
    end 

    res = [] 
    size = count_arr.size 
    size.times do |i| 
    count_arr[i].times do 
     res << i + min 
    end 
    end 

    res 
end 

p counting_sort([5, 22, 29, 39, 19, 51, 78, 96, 84]) 

Answer 2

如果你想研究algotirthms使用C或C++。

def bubble_sort(array) 
    sorted = array.dup 
    i  = 0 
    l  = sorted.length 

    while i < (l - 1) 
    j = 0 
    while j < l - i - 1 
     if sorted[j] > sorted[j + 1] 
     tmp   = sorted[j] 
     sorted[j]  = sorted[j + 1] 
     sorted[j + 1] = tmp 
     end 
     j += 1 
    end 
    i += 1 
    end 

    sorted 
end 

puts bubble_sort([5, 22, 29, 39, 19, 51, 78, 96, 84]) 

Answer 3

请注意，随着您的排序，您正在重新排列阵列。不要修改它，将其用作参考并将已排序的项目放入新阵列中。