In learning, there is no best approach generally. Best option should be to order data in a randomized way and use different k values and compare average performances.

The best approach is to select/arrange data randomly.

Basically you have three data sets: training, validation and testing.

You train the classifier using 'training set', tune the parameters using 'validation set' and then test the performance of your classifier on unseen 'test set'. An important point to note is that during training the classifier only the training and/or validation set is available. The test set must not be used during training the classifier. The test set will only be available during testing the classifier.

There is no 'one' way of choosing the size of training/testing set and people apply heuristics such as 10% testing and 90% training. However, doing so can bias the classification results and the results may not be generalizable. A well accepted method is N-Fold cross validation, in which you randomize the dataset and create N (almost) equal size partitions. Then choose Nth partition for testing and N-1 partitions for training the classifier. Within the training set you can further employ another K-fold cross validation to create a validation set and find the best parameters. And repeat this process N times to get an average of the metric. Since we want to get rid of classifier 'bias' we repeat this above process M times (by randomizing data and splitting into N fold) and take average of the metric.  Cross-validation is almost unbiased, but it can also be misused if training and validation set comes from different populations and knowledge from training set is used in the test set.

I think, the difference in accuracy is different not due to the arrangement of data. The ordering of data merely reflects in calculation of accuracy.

Let discuss the result, in case 1

train test split accuracy with test size 25% is 90%.

and accuracy with K fold CV 69% with std 0.07%

in case 2

train test split accuracy with test size 25% is 54%.

and accuracy with K fold CV 78% with std 0.08%

In all cases, data is shuffled and randomized

As random data u apply, as best training and testing u get....in matlab, u can rondom ur feature vectors by using the function rand perm for permutation randomization