Skip to content

Instantly share code, notes, and snippets.

@sunny0425

sunny0425/quick_sort.rb

Last active November 1, 2016 05:26
Show Gist options
  • Save sunny0425/65c9e0789677c98a185a5c9ea03cbb06 to your computer and use it in GitHub Desktop.
Save sunny0425/65c9e0789677c98a185a5c9ea03cbb06 to your computer and use it in GitHub Desktop.
Download ZIP
快速排序
Raw
quick_sort.rb
def quick_sort(arr)
len = arr.length
return arr if len == 1
old_index = 0
x = arr[old_index]
if len == 2
if arr[1] < x
arr[0] = arr[1]
arr[1] = x
end
end
i = 1
j = len - 1
while j > i
if arr[j].to_i < x
arr[old_index] = arr[j]
arr[j] = x
old_index = j
while i < j
if arr[i].to_i > x
arr[old_index] = arr[i]
arr[i] = x
old_index = i
break
end
i = i + 1
end
end
j = j - 1
end
sub_arr1 = quick_sort(arr[0..old_index])
sub_arr2 = quick_sort(arr[old_index+1..len-1])
arr = sub_arr1.concat(sub_arr2)
return arr
end
arr = [49,38,65,97,76,13,27,50]
quick_sort(arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment