一躁绸、淺談數(shù)組和鏈表
數(shù)組：具有相同類型的元素的集合。數(shù)組分配在一塊連續(xù)的數(shù)據(jù)空間上臣嚣，因此存儲(chǔ)效率低净刮，插入和刪除元素效率低，支持隨機(jī)訪問(wèn)硅则，訪問(wèn)元素效率高淹父。
鏈表(單向鏈表、雙向鏈表怎虫、循環(huán)鏈表)：鏈表是一種物理存儲(chǔ)單元上非連續(xù)暑认、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的大审。插入蘸际，刪除效率高，空間利用率高徒扶，不支持隨機(jī)訪問(wèn)粮彤，查找元素效率低
二、 選擇排序介紹：
1.方案一：第一次查找，找出數(shù)組中的最小元素导坟，交換至數(shù)組第一個(gè)位置屿良，第二次查找數(shù)組中除了第一個(gè)元素，剩下的部分惫周，找出最小元素交換至數(shù)組第二個(gè)位置尘惧，以此類推。闯两。褥伴。
2.方案二：第一次查找Array1，找出最小元素漾狼，取出來(lái)放到一個(gè)一開(kāi)始為空的數(shù)組Array2中重慢，并將Array1中的那個(gè)最小元素刪除，Array1長(zhǎng)度減1逊躁。第二次查找Array1似踱，找出最小元素，取出來(lái)放到一個(gè)數(shù)組Array2中稽煤，并將Array1中的那個(gè)最小元素刪除核芽。。酵熙。轧简。最后Array1長(zhǎng)度為0，Array2就是排序后的數(shù)組匾二。
方案一：
scala實(shí)現(xiàn)代碼：
object XuanZe{
def main(args:Array[String]){
var myArray = Array(45, 26, 34, 2, 888, 54, 23, 45, 76, 2);
selectSort(myArray);
for ( x <- myArray ) {
println( x )
}
}
def selectSort(array:Array[Int]):Unit={
var smallest_index:Int = 0;
var temp:Int = 0;
for(i <- 0 to (array.length - 2)){
smallest_index = i;
for(j <- (i+1) to (array.length -1)){
if(array(j)<array(smallest_index)){
smallest_index = j;
}
}
if(smallest_index != i){
temp = array(i);
array(i) = array(smallest_index);
array(smallest_index) = temp;
}
}
}
}
Java實(shí)現(xiàn)代碼：
import java.util.Arrays;
public class MyClass {
public static void main(String[] args){
int[] sortArray = {45, 26, 34, 2, 888, 54, 23, 45, 76, 2};
selectSort(sortArray);
System.out.println(Arrays.toString(sortArray));
}
private static void selectSort(int[] array){
int smallest_index = 0;
int temp = 0;
for(int i = 0;i<array.length-1;i++){
//無(wú)序區(qū)的最小數(shù)據(jù)數(shù)組下標(biāo)
smallest_index = i;
for(int j = i+1;j<array.length;j++){
//在無(wú)序區(qū)中找到最小數(shù)據(jù)并保存其數(shù)組下標(biāo)
if(array[j]<array[smallest_index]){
smallest_index = j;
}
}
//如果不是無(wú)序區(qū)的最小值位置不是默認(rèn)的第一個(gè)數(shù)據(jù)哮独，則交換之。
if(smallest_index != i){
temp = array[i];
array[i] = array[smallest_index];
array[smallest_index] = temp;
}
}
}
}
OC實(shí)現(xiàn)代碼：
主文件
#import <Foundation/Foundation.h>
#import "XuanZe.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
XuanZe *xz = [[XuanZe alloc] init];
NSMutableArray* array = (NSMutableArray*)@[@45, @26, @34, @2, @888, @54, @23, @45, @76, @2];
NSLog(@"%@",[xz selectionSort:array]);
}
return 0;
}
實(shí)現(xiàn)文件
#import "XuanZe.h"
@implementation XuanZe
-(NSMutableArray*)selectionSort:(NSMutableArray*)array{
int smallest_index = 0;
id temp;
NSMutableArray *arr = [NSMutableArray arrayWithArray:array];
for(int i = 0;i<[arr count];i++){
//無(wú)序區(qū)的最小數(shù)據(jù)數(shù)組下標(biāo)
smallest_index = i;
for(int j = i+1;j<[arr count];j++){
//在無(wú)序區(qū)中找到最小數(shù)據(jù)并保存其數(shù)組下標(biāo)
if(arr[j]<arr[smallest_index]){
smallest_index = j;
}
}
//如果不是無(wú)序區(qū)的最小值位置不是默認(rèn)的第一個(gè)數(shù)據(jù)察藐，則交換之皮璧。
if(smallest_index != i){
temp = arr[i];
arr[i] = arr[smallest_index];
arr[smallest_index] = temp;
}
}
return arr;
}
@end
Python實(shí)現(xiàn)代碼：
def selectionSort(arr):
for i in range(0,len(arr)):
min = i
for j in range(i+1,len(arr)):
if arr[j]<arr[min]:
min = j
arr[i],arr[min] = arr[min],arr[i]
return arr;
print(selectionSort([45,26,34,2,888,54,23,45,76,2]))
方案二：
scala實(shí)現(xiàn)代碼：
import scala.collection.mutable.ArrayBuffer
object XuanZe1{
def main(args:Array[String]){
var myArray = ArrayBuffer(45, 26, 34, 2, 888, 54, 23, 45, 76, 2);
var myArray1 = selectSort(myArray);
for ( x <- myArray1 ) {
println( x );
}
}
def selectSort(array:ArrayBuffer[Int]):ArrayBuffer[Int]={
var myArrayBuffer = ArrayBuffer(0,0,0,0,0,0,0,0,0,0);
var myArrayBuffer1 = array;
for(i <- 0 to (array.length - 1)){
var smallest_index:Int = findSmallest(myArrayBuffer1);
myArrayBuffer(i) = myArrayBuffer1(smallest_index);
myArrayBuffer1.remove(smallest_index);
}
return myArrayBuffer;
}
def findSmallest(array:ArrayBuffer[Int]):Int={
var smallest:Int = array(0);
var smallest_index:Int = 0;
for(i <- 1 to (array.length - 1)){
if(array(i)<smallest){
smallest = array(i);
smallest_index = i;
}
}
return smallest_index;
}
}
Java實(shí)現(xiàn)代碼：
import java.util.Arrays;
public class XuanZe {
public static void main(String[] args){
int[] sortArray = {45, 26, 34, 2, 888, 54, 23, 45, 76, 2};
System.out.println("排序結(jié)果"+Arrays.toString(selectionSort(sortArray)));
}
private static int[] selectionSort(int[] array){
int[] newArr = new int[10];
int[] array1 = array;
for(int i = 0;i<array.length;i++){
int smallest_index = finSmallest(array1);
newArr[i] = array1[smallest_index];
//去除最小值，數(shù)組縮容
array1[smallest_index] = array1[array1.length-1];
array1 = Arrays.copyOf(array1,array1.length-1);
System.out.println(Arrays.toString(array1));
}
return newArr;
}
private static int finSmallest(int[] arr){
//存儲(chǔ)最小的值
int smallest = arr[0];
//存儲(chǔ)最小值得索引
int smallest_index = 0;
for(int i = 1; i< arr.length;i++){
if(arr[i] < smallest){
smallest = arr[i];
smallest_index = i;
}
}
return smallest_index;
}
}
結(jié)果展示:
SYJ.png
OC實(shí)現(xiàn)代碼：
主文件
#import <Foundation/Foundation.h>
#import "XuanZe.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
XuanZe *xz = [[XuanZe alloc] init];
NSLog(@"%@",[xz selectionSort:(NSMutableArray*)@[@45, @26, @34, @2, @888, @54, @23, @45, @76, @2]]);
}
return 0;
}
XuanZe.m文件
#import "XuanZe.h"
@implementation XuanZe
-(NSMutableArray*)selectionSort:(NSMutableArray*)array{
NSMutableArray *array1 = [[NSMutableArray alloc] initWithArray:array];
NSMutableArray *newArray = [[NSMutableArray alloc] initWithCapacity:0];
for(int i = 0;i<[array count];i++){
int smallest_index = [self findSmallest:array1];
newArray[i] = array1[smallest_index];
//去除最小值
[array1 removeObjectAtIndex:smallest_index];
}
return newArray;
}
-(int)findSmallest:(NSMutableArray*)array{
//存儲(chǔ)最小的值
int smallest = (int)array[0];
//存儲(chǔ)最小值的索引
int smallest_index = 0;
for(int i = 1; i< [array count];i++){
if((int)array[i] < smallest){
smallest = (int)array[i];
smallest_index = i;
}
}
return smallest_index;
}
@end
結(jié)果展示：
SYJ.png
Python實(shí)現(xiàn)代碼：
def findSmallest(arr):
#存儲(chǔ)最小的值
smallest = arr[0]
#存儲(chǔ)最小值的索引
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest_index = findSmallest(arr)
#取出數(shù)組中最小的元素并將其加入到新的數(shù)組中
newArr.append(arr.pop(smallest_index))
return newArr
print(selectionSort([45,26,34,2,888,54,23,45,76,2]))
結(jié)果展示：
SYJ.png
